LEPP-Delaunay algorithm: a robust tool for producing size-optimal quality triangulations

Proceedings, 8th International Meshing Roundtable, South Lake Tahoe, CA, U.S.A., pp.205-220, October 1999

MESHING
RESEARCH
CORNER

Abstract
The LEPP-Delaunay algorithm for the quality triangulation problem can be formulated in terms of the Delaunay insertion of midpoints of terminal edges (the common longest-edge of a pair of Delaunay triangles) and boundary edges in the current mesh. In this paper we discuss theoretical results essentially based on the study of the triangle improvement properties of the basic point insertion operations, which precisely explain the observed practical behavior. We prove that optimal-size triangulations (within a con-stant factor near to 1), with smallest-angle greater than or equal to 30 are produced, excepting occasionally some isolated angles 22.20 < a < 300 related with non-frequent geometric conditions and boundary restrictions. The algorithm has a fast convergence behavior for attaining around 250 which approximately produces a radial "binary partition" point distribution around small geometric details; and a reasonable slower con-vergence for attaining the 300.

Download Full Paper (Postscript Format)