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. (C) 2019 Elsevier B.V. All rights reserved.