Longest-Edge Algorithms: Nondegeneracy Properties in 3 Dimensions

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

Maria-Cecilia Rivara
Department of Computer Science, University of Chile
mcrivara@dcc.uchile.cl

Angel Plaza
Department of Las Palmas de la Gran Canaria
aplaza@dma.ulpgc.es

Abstract
Longest-edge algorithms have become useful and flexible mathematical tools not only for the quality refinement of quality unstructured triangulations but also for the improvement of bad-quality Delaunay meshes [Rivara, International Journal for Numerical Methods in Engineering, 1997]. However until 1998, there had not been mathematical results available guaranteeing the non-degeneracy properties of the 3- dimensional mesh.

The first nondegeneracy properties on a 3-dimensional refinement algorithm (fill-ing a gap in the theory) are discussed in this paper. These have been obtained by studying an 8-tetrahedra longest-edge algorithm which generalizes the 4 triangles longest-edge refinement algorithm. Statistical and fractal nondegeneracy properties over this 3D refinement algorithm have been proved: (1) the asymptotic average number of tetrahedra surrounding each vertex is equal to 24; (2) the number of tetrahedra sourrounding each fixed vertex remains constant after a few local itera-tive refinement around such vertex; and (3) the algorithm improves each triangular face produced as the refinement proceeds. Empirical study not only supports these results but also shows that, consistently throughout the refinement levels both the distribution of quality tetrahedra and the volume percentage covered by better tetra-hedra tend to be improved, and that the distribution of the number of tetrahedra surrounding each vertex tends to have a constant standard deviation around a mean value that rapidly approaches the asymptotic value.