One the main properties of Delaunay triangulation is that, for a given set of nodes, it provides the maximum smallest angle among all possible triangulations. It is this property that supports the wide usage of Delaunay algorithms in the mesh generation problems. However, it doesn't guarantee that the smallest angle will always be small. In fact, for some point distributions, it is impossible to avoid skinny small-angle triangles. The remedy is to add additional nodes to the triangulation so that the quality of the triangles is globally improved. This problem has become known as mesh refinement Ruppert (1995).
 |
One of the recently proposed mesh refinement algorithms is Rivara's backward longest-side refinement technique Rivara (1996). The main idea of the algorithm is to trace the LSPP (longest-side propagation path) for each refined triangle. The LSPP is an ordered list of triangles, connected by a common edge, such that the longest triangle edge is strictly increasing. After tracing the LSPP, we bisect the longest edge and insert its midpoint into the triangulation. Rivara's algorithm is remarkably efficient and easy to implement. In comparison with alternative methods, it has the additional advantage of being applicable in three dimensions.
Figure 14 demonstrates an application of different triangulation techniques to a simple layered model, borrowed from the Seismic Unix demos (where it is attributed it to V.Cervený.) Another model from Hale and Cohen (1991) is used in Figure 15.
 |
 |