Ruppert's algorithm: Difference between revisions

Revision as of 20:54, 1 August 2010

Revision as of 20:59, 1 August 2010

Line 33:

Jim Ruppert discovered this algorithm in the early 1990s.<ref>{{cite journal | doi=10.1006/jagm.1995.1021 | first=Jim | last=Ruppert | title=A Delaunay refinement algorithm for quality 2-dimensional mesh generation | journal=Journal of Algorithms | year=1995 | issue=3 | pages= 548–585 | volume=18}}</ref>

Since then, various small improvements have been made.<ref>{{cite conference journal| first1=Gary | last1=Miller | first2=Steven | last2=Pav | first3=Noel | last3=Walkington | title=When and why Ruppert'sDelaunay algorithmrefinement worksalgorithms work | booktitlejournal=ProceedingsInternational Journal of theComputational 12thGeometry Internationaland Meshing RoundtableApplications | year=20032005 | volume=15 | issue=1 | pages=91–10225-54}}</ref>

An extension of Ruppert's algorithm in two dimensions is implemented in the freely available (yet non-[[Free software|free]]) [http://www.cs.cmu.edu/~quake/triangle.html Triangle] package.

Ruppert's algorithm has been shown to terminate for any input PLS with no small angles. The algorithm can be extended to handle any input by slightly relaxing the quality requirement on the output (Miller et al., 20032005).

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