carrier image

The Cost of Compatible Refinement of Simplex Decomposition Trees

Atalay, F. Betul and David M. Mount

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


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.

David M. Mount
Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD.

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)

Contact author(s) or publisher for availability and copyright information on above referenced article