Ruppert's algorithm: Difference between revisions

Revision as of 02:06, 17 January 2015

Revision as of 19:15, 24 November 2015

Line 65:

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 (journal)|Computational Geometry: Theory and Applications]] | year=2002 | volume=22 | issue=1–3 | pages=21–74 | doi=10.1016/s0925-7721(01)00047-5}}</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.06 degrees.<ref>{{cite arXiv|last=Rand|first=Alexander|title=Improved Examples of Non-Termination for Ruppert's Algorithm|year=2011|eprint=1103.3903|class=cs.CG }}.</ref>

== See also ==