Ruppert's algorithm: Difference between revisions

Revision as of 14:39, 19 November 2010

Revision as of 01:56, 6 January 2011

Line 45:

Ruppert's algorithm can be naturally extended to three dimensions, however its output guarantees are somewhat weaker due to the sliver type tetrahedron.

An extension of Ruppert's algorithm in two dimensions is implemented in the freely available Triangle package. Two variants of Ruppert's algorithm in this package are guaranteed to terminate for a poor-quality threshold of about 26.5 degrees.<ref>{{cite journal | first1=Jonathan | last1=Shewchuk | title=Delaunay refinement algorithms for triangular mesh generation | journal=Computational Geometry: Theory and Applications | year=2002 | volume=22 | issue=1-3 | pages=21–74}}</ref> In practice these algorithms are successful for poor-quality thresholds over 30 degrees. However, examples are known which cause the algorithm to fail with a threshold greater than 29.51 degrees.<ref>{{citation|last=Rand|first=Alexander|title=On the non-termination of Ruppert's algorithm|year=2011|id={{arxiv|1101.1071}}}}.</ref>

== See also ==