Research credit, references, and online papers


A paper discussing some aspects of Triangle is available. Of course, I can take credit for only a fraction of the ideas that made this mesh generator possible. Triangle owes its existence to the efforts of many fine computational geometers and other researchers; some are listed below.

Triangle is based on Ruppert's Delaunay refinement algorithm for quality triangular mesh generation.

Ruppert's algorithm evolved from important earlier work. Triangle's implementation of the divide-and-conquer and incremental Delaunay triangulation algorithms follows closely the presentation of Guibas and Stolfi, even though I use a triangle-based data structure instead of their quad-edge data structure. The O(n log n) divide-and-conquer algorithm promoted by Guibas and Stolfi was originally developed by Lee and Schachter. Dwyer showed that the algorithm is improved by using alternating vertical and horizontal cuts to divide the point set. Though many researchers have forgotten, the incremental insertion algorithm for Delaunay triangulation was originally proposed by Lawson. Triangle uses an expected O(n1/3) time point location scheme proposed by Mücke, Saias, and Zhu. Guibas, Knuth, and Sharir show that if the order of point insertion is randomized, each point can be inserted in O(n) time, not counting point location. (Triangle does not currently randomize the order of point insertion, but one can nevertheless expect the incremental insertion algorithm to run in O(n4/3) time on most point sets.) Triangle's O(n log n) sweepline algorithm for Delaunay triangulation is due to Fortune, and relies upon Sleator and Tarjan's splay trees. The routines for the exact orientation and incircle tests. See the Robust Predicates page for more information about this research, or to access C source code for exact arithmetic and robust geometric predicates. A very abbreviated version of the above. The two papers above owe a large debt to three others. And finally, the survey I simply couldn't have done without.
Return to Triangle home page.
jrs@cs.cmu.edu