Research credit, references, and online papers
A paper discussing some aspects of Triangle is available.
-
Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh
Generator and Delaunay Triangulator, First Workshop on Applied
Computational Geometry (Philadelphia, Pennsylvania), pages 124-133,
ACM, May 1996.
Abstract (with BibTeX citation),
PostScript (513k, 10 pages), and
HTML.
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.
-
Jim Ruppert, A Delaunay Refinement Algorithm for Quality 2-Dimensional
Mesh Generation, Journal of Algorithms 18(3):548-585, May 1995.
Abstract (with BibTeX citation),
PostScript (1526k).
Ruppert's algorithm evolved from important earlier work.
-
L. Paul Chew, Guaranteed-Quality Triangular Meshes,
Technical Report TR-89-983, Department of Computer Science,
Cornell University, 1989.
-
Marshall Bern, David Eppstein, and John R. Gilbert, Provably Good Mesh
Generation, Journal of Computer and System Sciences 48(3):384-409,
June 1994.
Abstract (with BibTeX citation),
PostScript (695k).
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.
-
Leonidas J. Guibas and Jorge Stolfi, Primitives for the Manipulation
of General Subdivisions and the Computation of Voronoï Diagrams, ACM
Transactions on Graphics 4(2):74-123, April 1985.
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.
-
Der-Tsai Lee and Bruce J. Schachter, Two Algorithms for Constructing
the Delaunay Triangulation, International Journal of Computer and
Information Science 9(3):219-242, 1980.
-
Rex A. Dwyer, A Faster Divide-and-Conquer Algorithm for Constructing
Delaunay Triangulations, Algorithmica 2(2):137-151, 1987.
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.)
-
C. L. Lawson, Software for C1 Surface Interpolation, in
Mathematical Software III, John R. Rice, editor, Academic Press,
New York, pp. 161-194, 1977.
-
Ernst P. Mücke, Isaac Saias, and Binhai Zhu, Fast Randomized Point
Location Without Preprocessing in Two- and Three-dimensional Delaunay
Triangulations, Proceedings of the Twelfth Annual Symposium on
Computational Geometry, ACM, May 1996.
Abstract (with BibTeX citation),
PostScript.
-
Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir, Randomized
Incremental Construction of Delaunay and Voronoï Diagrams,
Algorithmica 7(4):381-413, 1992.
Triangle's O(n log n) sweepline algorithm for Delaunay
triangulation is due to Fortune, and relies upon Sleator and Tarjan's
splay trees.
-
Steven Fortune, A Sweepline Algorithm for Voronoï Diagrams,
Algorithmica 2(2):153-174, 1987.
-
Daniel Dominic Sleator and Robert Endre Tarjan, Self-Adjusting Binary Search
Trees, Journal of the ACM 32(3):652-686, July 1985.
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.
-
Jonathan Richard Shewchuk, Adaptive Precision Floating-Point
Arithmetic and Fast Robust Geometric Predicates,
Discrete & Computational Geometry 18:305-363, 1997.
Also Technical Report CMU-CS-96-140, School of Computer Science,
Carnegie Mellon University, Pittsburgh, Pennsylvania, May 1996.
Abstract (with BibTeX citation),
PostScript (676k, 53 pages).
A very abbreviated version of the above.
-
Jonathan Richard Shewchuk, Robust Adaptive Floating-Point Geometric
Predicates, Proceedings of the Twelfth Annual Symposium on
Computational Geometry, pages 141-150, ACM, May 1996.
Abstract (with BibTeX citation),
PostScript (310k, 10 pages).
Includes a good description of the key points,
but leaves out all the proofs and many details.
Presents a slower version of the addition algorithm because
there wasn't room to explain the fastest one.
The two papers above owe a large debt to three others.
-
Douglas M. Priest, Algorithms for
Arbitrary Precision Floating Point Arithmetic, Tenth Symposium on
Computer Arithmetic, pp. 132-143, IEEE Computer Society Press, 1991.
Abstract (with BibTeX citation),
Copyright notice (please read),
PostScript (240k).
-
Steven Fortune and Christopher J. Van Wyk, Efficient Exact Arithmetic
for Computational Geometry, Proceedings of the Ninth Annual Symposium
on Computational Geometry, pp. 163-172, Association for Computing Machinery,
May 1993.
-
Steven Fortune, Numerical Stability of Algorithms for 2D Delaunay
Triangulations, International Journal of Computational
Geometry & Applications 5(1-2):193-213, March-June 1995.
And finally, the survey I simply couldn't have done without.
-
Marshall Bern and David Eppstein, Mesh Generation and Optimal
Triangulation, pp. 23-90 of Computing in Euclidean Geometry,
Ding-Zhu Du and Frank Hwang (editors), World Scientific,
Singapore, 1992.
Abstract (with BibTeX citation),
PostScript (5,348k).
Return to Triangle home page.
jrs@cs.cmu.edu