The Cost of Compatible Refinement of Simplex Decomposition Trees

Proceedings, 15th International Meshing Roundtable, Springer-Verlag, pp.57-70, September 17-20 2006

MESHING
RESEARCH
CORNER

15th International Meshing Roundtable
Birmingham, Alabama, U.S.A.
September 17-20, 2006

F. Betul Atalay
Mathematics and Computer Science Department, Saint Joseph’s University, Philadelphia, PA.
fatalay@sju.edu

David M. Mount
Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD.
mount@cs.umd.edu

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 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.

Download Full Paper (PDF Format)