carrier image

On the Termination of Ruppertís Algorithm

Alexander Rand

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? [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 non-acute; 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