Research credit, references, and online papers

Two papers discussing Triangle are available. The first one is primarily concerned with the Triangle software, data structures, and implementation details. The second one is solely concerned with the algorithms that Triangle implements (and it mentions Triangle only once).

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's high-quality mesh generation is based on Delaunay refinement algorithms by Paul Chew and Jim Ruppert. (Both are surveyed in my article of Delaunay refinement algorithms above, and I have a description of Ruppert's Delaunay refinement algorithm here.) These algorithms evolved from important earlier work. The Ruppert/Chew Delaunay refinement method is modified in Triangle to handle domains with small angles well, following an idea in the innocuously titled yet very important paper of Miller, Pav, and Walkington. It also incorporates a modification by Üngör that reduces the number of triangles generated. 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 vertex 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. Clarkson and Shor show that if the order of vertex insertion is randomized, each vertex can be inserted in O(n) time, not counting point location. (Triangle does not currently randomize the order of vertex insertion, but one can nevertheless expect the incremental insertion algorithm to run in O(n4/3) time on most vertex 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 following two papers describe the routines for the exact orientation and incircle tests, which make Triangle more numerically robust. The second paper is a very abbreviated version of the first. See the Robust Predicates page for more information about this research, or to access C source code for exact arithmetic and robust geometric predicates. 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.