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.

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

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.

Mon Aug 12 10:28:49 EDT 1996