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).

Figure 13

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.

Figure 14

Figure 15

10/9/1997