Bounds on the cost of compatible refinement of simplex decomposition trees in arbitrary dimensions

Abstract A hierarchical simplicial mesh is a recursive decomposition of space into cells that are simplices. Such a mesh is compatible if pairs of neighboring cells meet along a single common face. Compatibility condition is important in many applications where the mesh serves as a discretization of a function. Enforcing compatibility involves refining the simplices further if they share split faces with their neighbors, thus generates a larger mesh. We prove a tight upper bound on the expansion factor for 2-dimensional meshes, and show that the size of a simplicial subdivision grows by no more than a constant factor when compatibly refined. We also prove upper bounds for d -dimensional meshes.