The cost of compatible refinement of simplex decomposition trees

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 of the mesh further, thus generates a larger mesh. We show that the size of a simplicial mesh grows by no more than a constant factor when compatibly refined. We prove a tight upper bound on the expansion factor for 2-dimensional meshes, and we sketch upper bounds for d-dimensional meshes.