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

Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh
Generator and Delaunay Triangulator, in ``Applied Computational
Geometry: Towards Geometric Engineering'' (Ming C. Lin and Dinesh Manocha,
editors), volume 1148 of Lecture Notes in Computer Science, pages 203222,
SpringerVerlag, Berlin, May 1996. (From the First ACM Workshop on
Applied Computational Geometry.)
Abstract (with BibTeX citation),
PostScript (513k, 10 pages), and
HTML.

Jonathan Richard Shewchuk, Delaunay Refinement Algorithms for Triangular
Mesh Generation, Computational Geometry:
Theory and Applications 22(13):2174, May 2002.
PostScript (5,128k, 54 pages).
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 highquality 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.)

L. Paul Chew, GuaranteedQuality Mesh Generation for Curved Surfaces,
Proceedings of the Ninth Annual Symposium on Computational Geometry
(San Diego, California), pages 274280, Association for Computing Machinery,
May 1993.
Available from
the ACM Digital Library.

Jim Ruppert, A Delaunay Refinement Algorithm for Quality 2Dimensional
Mesh Generation, Journal of Algorithms 18(3):548585, May 1995.
PostScript (1526k).
These algorithms evolved from important earlier work.

L. Paul Chew, GuaranteedQuality Triangular Meshes,
Technical Report TR89983, 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):384409,
June 1994.
PostScript (695k).
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.

Gary L. Miller, Steven E. Pav, and Noel J. Walkington, When and Why
Ruppert's Algorithm Works, Twelfth International Meshing Roundtable,
pages 91102, Sandia National Laboratories, September 2003.
PDF (664k, 12 pages).

Alper Üngör, Offcenters:
A New Type of Steiner Points for Computing
SizeOptimal QualityGuaranteed Delaunay Triangulations,
Proceedings of LATIN 2004 (Buenos Aires, Argentina), April 2004.
PDF (320k, 10 pages).
Triangle's implementation of the divideandconquer and incremental
Delaunay triangulation algorithms follows closely the presentation of
Guibas and Stolfi, even though I use a
trianglebased data structure
instead of their quadedge data structure.

Leonidas J. Guibas and Jorge Stolfi, Primitives for the Manipulation
of General Subdivisions and the Computation of Voronoi Diagrams, ACM
Transactions on Graphics 4(2):74123, April 1985.
Available from
the ACM Digital Library.
The O(n log n) divideandconquer 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.

DerTsai Lee and Bruce J. Schachter, Two Algorithms for Constructing
the Delaunay Triangulation, International Journal of Computer and
Information Science 9(3):219242, 1980.

Rex A. Dwyer, A Faster DivideandConquer Algorithm for Constructing
Delaunay Triangulations, Algorithmica 2(2):137151, 1987.
Though many researchers have forgotten, the incremental insertion algorithm
for Delaunay triangulation was originally proposed by Lawson. Triangle
uses an expected O(n^{1/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(n^{4/3}) time on most vertex sets.)

C. L. Lawson, Software for C^{1} Surface Interpolation, in
Mathematical Software III, John R. Rice, editor, Academic Press,
New York, pp. 161194, 1977.

Ernst P. Mücke, Isaac Saias, and Binhai Zhu, Fast Randomized Point
Location Without Preprocessing in Two and Threedimensional Delaunay
Triangulations, Proceedings of the Twelfth Annual Symposium on
Computational Geometry, Association for Computing Machinery, May 1996.
PostScript.

Kenneth L. Clarkson and Peter W. Shor, Applications of Random Sampling
in Computational Geometry II,
Discrete & Computational Geometry 4(1):387421, 1989.
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 Voronoi Diagrams,
Algorithmica 2(2):153174, 1987.

Daniel Dominic Sleator and Robert Endre Tarjan, SelfAdjusting Binary Search
Trees, Journal of the ACM 32(3):652686, July 1985.
Available from
the ACM Digital Library.
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.

Jonathan Richard Shewchuk, Adaptive Precision FloatingPoint
Arithmetic and Fast Robust Geometric Predicates,
Discrete & Computational Geometry 18:305363, 1997.
Also Technical Report CMUCS96140, School of Computer Science,
Carnegie Mellon University, Pittsburgh, Pennsylvania, May 1996.
Abstract (with BibTeX citation),
PostScript (676k, 53 pages).

Jonathan Richard Shewchuk, Robust Adaptive FloatingPoint Geometric
Predicates, Proceedings of the Twelfth Annual Symposium on Computational
Geometry, pages 141150, Association for Computing Machinery, 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. 132143, IEEE Computer Society Press, 1991.
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. 163172, Association for Computing Machinery,
May 1993.
Available from
the ACM Digital Library.

Steven Fortune, Numerical Stability of Algorithms for 2D Delaunay
Triangulations, International Journal of Computational
Geometry & Applications 5(12):193213, MarchJune 1995.
And finally, the survey I simply couldn't have done without.

Marshall Bern and David Eppstein, Mesh Generation and Optimal
Triangulation, pp. 2390 of Computing in Euclidean Geometry,
DingZhu Du and Frank Hwang (editors), World Scientific,
Singapore, 1992.
PostScript (5,348k).
Return to Triangle home page.