New longest-edge algorithms for the refinement and/or improvement of unstructured triangulations

In this paper I introduce a new mathematical tool for dealing with the reÞnement and/or the improvement of unstructured triangulations: the Longest-Edge Propagation Path associated with each triangle to be either reÞned and/or improved in the mesh. This is deÞned as the (Þnite) ordered list of successive neighbour triangles having longest-edge greater than the longest edge of the preceding triangle in the path. This ideal is used to introduce two kinds of algorithms (which make use of a Backward Longest-Edge point insertion strategy): (1) a pure Backward Longest-Edge ReÞnement Algorithm that produces the same triangulations as previous longest-edge algorithms in a more e¦cient, direct and easy-to-implement way; (2) a new Backward Longest-Edge Improvement Algorithm for Delaunay triangulations, suitable to deal (in a reliable, robust and e¤ective way) with the three important related aspects of the (triangular) mesh generation problem: mesh reÞnement, mesh improvement, and automatic generation of good-quality surface and volume triangulation of general geometries including small details. The algorithms and practical issues related with their implementation (both for the polygon and surface quality triangulation problems) are discussed in this paper. In particular, an e¤ective boundary treatment technique is also discussed. The triangulations obtained with the LEPPÐDelaunay algorithm have smallest angles greater than 30¡ and are, in practice, of optimal size. Furthermore, the LEPPÐDelaunay algorithms naturally generalize to threedimensions.