Terminal-edges Delaunay (small-angle based) algorithm for the quality triangulation problem

The terminal-edge Delaunay algorithm, initially called Lepp-Delaunay algori thm, deals with the construction of size-optimal (adapted to the geometry) quality triangulation of complex objects. In two dimensions, the algorithm can be formulated in terms of the Delaunay insertion of both midpoints of t erminal edges (the common longest-edge of a pair of Delaunay triangles) and midpoints of boundary related edges in the current mesh. For the processin g of a small angled triangle in the current mesh, the terminal-edge is foun d as the final longest-edge of the finite chain of triangles that neighbor on a longest edge - the longest edge propagating path of the small angled t riangle. Three boundary-related point insertion operations, which prevent n onconvergence behavior, are discussed in detail. The triangle improvement p roperties of the point insertion operations are used to prove that optimal- size triangulations, with smallest-angle greater than or equal to 30 degree s are always produced. (C) 2001 Elsevier Science Ltd. All rights reserved.