carrier image

An Analysis of Shewchukís DelaunayRefinement Algorithm

Si, Hang

Proceedings, 18th International Meshing Roundtable, Springer-Verlag, pp.498-518, October 25-28 2009


18th International Meshing Roundtable
Salt Lake City, UT, USA.
October 25-28, 2009

Weierstrass Institute for Applied Analysis and Stochastics (WIAS), Berlin

Shewchukís Delaunay refinement algorithm is a simple scheme to efficiently tetrahedralize a 3D domain. The original analysis provided guarantees on termination and output edge lengths. However, the guarantees are weak and the time and space complexity are not fully covered. In this paper, we present a new analysis of this algorithm. The new analysis reduces the original 90 degrees requirement for the minimum input dihedral angle to arccos 1/3 approximatly equal to 70.53 degrees. The bounds on output edge lengths and vertex degrees are improved. For a set of n input points with spread delta (the ratio between the longest and shortest pairwise distance), we prove that the number of output points is O(n log[delta]). In most cases, this bound is equivalent to O(n log n). This theoretically shows that the output number of tetrahedra is small.

Download Full Paper (PDF Format)

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