A Negative Result on Quality Triangulations

For any angle bound > 0, there exists a PSLG such that it is not possible to triangulate without creating a new corner (not present in ) having angle smaller than . Here, I discuss why this is true.

Ruppert's proof that his Delaunay refinement algorithm terminates makes use of the assumption that all interior angles are 90^o or larger. This condition is often violated in practice, so he suggests handling small interior angles by surrounding each vertex of an acute angle with a ring of shield edges. As the negative result stated above suggests, there are PSLGs for which shield edges fail, and for which no construction can succeed. Fortunately, all such PSLGs I am aware of have an interior angle much smaller than 30^o, so failure is generally predictable.

   

Figure 15: In any triangulation with no angles smaller than 30^o, the ratio b/a cannot exceed 27.

The reasoning behind the result is as follows. Suppose a segment in a conforming triangulation has been split into two subsegments of lengths a and b, as illustrated in Figure 15. Mitchell [13] proves that if the triangulation has no angles smaller than , then the ratio b/a has an upper bound of . (This bound is tight if 180^o/ is an integer; Figure 15 offers an example where the bound is obtained.) Hence any bound on the smallest angle of a triangulation imposes a limit on the gradation of triangle sizes along a segment (or anywhere in the mesh).

A problem can arise if a small angle occurs at the intersection point o of two segments of a PSLG, as illustrated in Figure 16 (top). The small angle cannot be improved, of course, but one does not wish to create any new small angles. Assume that one of the segments is split by a point p, which may be present in the input or may be inserted to help achieve the angle constraint elsewhere in the triangulation. The insertion of p forces part of the region between the two segments to be triangulated (Figure 16, center), which can cause a new point q to be inserted on the segment containing p. Let and as illustrated. If the angle bound is maintained, the length a cannot be large; the ratio b/a is bounded below

   

Figure 16: Top: A difficult PSLG with a small interior angle . Center: The point p and the angle constraint necessitate the insertion of the point q. Bottom: The point q and the angle constraint necessitate the insertion of the point r. The process repeats eternally.

If the region above the segments is part of the interior of the PSLG, the fan effect demonstrated in Figure 15 may necessitate the insertion of another vertex r between o and p (Figure 16, bottom); this circumstance is unavoidable if the product of the bounds on b/a and a/b given above is less than one. For an angle constraint of = 30^o, this condition occurs when is about six tenths of a degree. Unfortunately, the new vertex r creates the same conditions as the vertex p, but closer to o; the process will cascade, eternally creating smaller and smaller triangles in an attempt to satisfy the angle constraint. No algorithm can produce a finite triangulation of such a PSLG without violating the angle constraint. (It is amusing to consider whether the angle constraint can be met if one is allowed an infinite number of triangles.)

If some PSLGs do not have quality triangulations, what are the implications for shielding? Triangle implements a variant of shielding known as ``modified segment splitting using concentric circular shells'' (see Ruppert [15] for details), which is generally effective in practice for PSLGs that have small angles greater than 5^o, and often for smaller angles. Shielding is useful even though it cannot solve all problems. On the other hand, the Delaunay refinement algorithm does not know to use careful arrangements of triangles as in Figure 15 to manage small input angles, and therefore can fail to terminate even on PSLGs for which a quality triangulation exists. Hence, Triangle prints a warning message when angles smaller than five degrees appear between input segments. The smaller an angle is, and the greater the number of small angles in a PSLG, the less likely Triangle is to terminate. An interesting question for future work is how to determine when and where it is wise to weaken the angle constraint so that termination can be ensured.

This problem presents another motivation for removing triangles from holes and concavities prior to applying the Delaunay refinement algorithm. Holes with small angles might cause the algorithm to fail if triangles are not removed until after refinement. Concave objects can be particularly dastardly, because a very small angle may occur between a defining segment of the object and an edge of the convex hull. The user, unaware of the effect of the convex hull edge, would be mystified why the Delaunay refinement algorithm fails to terminate on what appears to be a simple PSLG. (In fact, this is how the issues described in this section first became evident to me.) Early removal of triangles from concavities avoids this problem.