
On the Termination of Ruppertís Algorithm
Alexander Rand
Research Notes, 19th International Meshing Roundtable, SpringerVerlag, pp.Research Note, October 36 2010

IMR PROCEEDINGS

19th International Meshing Roundtable
Chattanooga, Tennessee, USA.
October 36, 2010
University of TexasAustin
Email: arand@ices.utexas.edu
Summary
For a nonacute planar straightline 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? [5], 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 [6] 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 [3] 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 [2]. Many other
variants of Ruppertís algorithm have been designed to relax or eliminate the
requirement that the input be nonacute; see [4] 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
