On the Termination of Ruppertís Algorithm
Research Notes, 19th International Meshing Roundtable, Springer-Verlag, pp.Research Note, October 3-6 2010
19th International Meshing Roundtable
Chattanooga, Tennessee, USA.
October 3-6, 2010
University of Texas-Austin
For a non-acute planar straight-line graph, Ruppertís algorithm produces a
conforming Delaunay triangulation composed of triangles containing no angles
less than . Ruppert proved the algorithm terminates for all / 20.7? , but
this constraint has been seen to be overly conservative in practice. Ruppert
observed that the minimum angle reaches 30? during typical runs of the algorithm.
Further experimentation by Shewchuk  suggested that even higher
values are admissible: "In practice, the algorithm generally halts with an angle
constraint of 33.8?, but often fails [at] 33.9?."
The constraint on can be improved to about 26.5? by splitting adjacent
segments at equal length  or modifying the algorithm [1, 7]. Certain
modifications of the vertex insertion procedure have also been demonstrated
that this constraint can be improved to possibly 40? or more . Many other
variants of Ruppertís algorithm have been designed to relax or eliminate the
requirement that the input be non-acute; see  for a comprehensive investigation.
However, no improvement has been proved for the minimum angle
constraint for Ruppertís original algorithm.
For each variant of the algorithm, theoretical requirement falls short of
the observed behavior. We aim to study this gap for the original algorithm
with the hope that a precise analysis of its behavior will lead to a better
understanding of the subsequent improvements. There are three parts of this
investigation. First, we give a counterexample demonstrating that Ruppertís
algorithm can fail to terminate for ò 30.7?. Second, several experiments of
Ruppertís algorithm using random inputs are considered. Finally, we prove
that Ruppertís algorithm terminates for all / 22.2?..
Download Full Paper (PDF Format)
Contact author(s) or publisher for availability and copyright information on above referenced article