Ruppert's algorithm: Difference between revisions

Revision as of 13:18, 15 April 2010

Revision as of 13:45, 15 April 2010

Line 28:

According to Shewchuk,

"Ruppert's algorithm for two-dimensional quality mesh generation is perhaps the first theoretically guaranteed meshing algorithm to be truly satisfactory in practice."<ref>{{cite web | last = Shewchuk | first = Jonathan | title = Ruppert's Delaunay Refinement Algorithm | url = http://www.cs.cmu.edu/~quake/tripaper/triangle3.html | accessdate = April 2010}}</ref>

[http://www.cs.cmu.edu/~quake/tripaper/triangle3.html "Ruppert's Delaunay Refinement Algorithm"] by Jonathan Richard Shewchuk

</ref>

Jim Ruppert discovered this algorithm in the early 1990s.<ref>{{cite journal | 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 | first=Gary | last=Miller | coauthors=Steven Pav, Noel Walkington | title=When and why Ruppert's algorithm works | booktitle=Proceedings of the 12th International Meshing Roundtable | year=2003 | pages=91-102}}</ref>

[http://ccom.ucsd.edu/~spav/work/index.html Steven Elliot Pav: Research]

</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.

Line 49 ⟶ 45:

* [[Voronoi diagram]]

* [[Polygon mesh]]

==Notes==

{{Reflist}}<!--added under references heading by script-assisted edit-->

== References ==

{{Reflist}}

* G. L. Miller, S. E. Pav, and N. J. Walkington. When and why Ruppert's algorithm works. In Proceedings of the 12th International Meshing Roundtable, pages 91-102. Sandia National Laboratory, September 2003.

* J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation, 1995.

== External links ==

* {{cite web

| last = Pav | first = Steven

| title = Research

[ | url = http://ccom.ucsd.edu/~spav/work/index.html Steven Elliot Pav: Research]

| accessdate = April 2010

}}

* {{cite web

| last = Rineau | first = Laurent

| title = 2D Conforming Triangulations and Meshes

| url = http://www.cgal.org/Manual/last/doc_html/cgal_manual/Mesh_2/Chapter_main.html

| accessdate = April 2010

}}

* {{cite web

| last = Shewchuk | first = Jonathan

| title = Triangle: A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.

| url = http://www.cs.cmu.edu/~quake/triangle.html

| accessdate = April 2010

}}

* {{cite web

| last = Si | first = Hang

| title = TetGen: A Quality Tetrahedral Mesh Generator and a 3D Delaunay Triangulator

| url = http://tetgen.berlios.de/

| accessdate = April 2010

}}

[[Category:Geometric algorithms]]