Research credit, references, and online papers (original) (raw)

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 203-222, Springer-Verlag, Berlin, May 1996. (From the First ACM Workshop on Applied Computational Geometry.) Abstract (with BibTeX citation), PostScript (513k, 10 pages), andHTML.
• Jonathan Richard Shewchuk, Delaunay Refinement Algorithms for Triangular Mesh Generation, Computational Geometry: Theory and Applications 22(1-3):21-74, 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 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 ofRuppert's Delaunay refinement algorithm here.)

• L. Paul Chew, Guaranteed-Quality Mesh Generation for Curved Surfaces, Proceedings of the Ninth Annual Symposium on Computational Geometry (San Diego, California), pages 274-280, Association for Computing Machinery, May 1993.Available from the ACM Digital Library.
• Jim Ruppert, A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Journal of Algorithms 18(3):548-585, May 1995. PostScript (1526k). These algorithms 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. 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 91-102, Sandia National Laboratories, September 2003. PDF (664k, 12 pages).
• Alper Üngör, Off-centers: A New Type of Steiner Points for Computing Size-Optimal Quality-Guaranteed Delaunay Triangulations, Proceedings of LATIN 2004 (Buenos Aires, Argentina), April 2004. PDF (320k, 10 pages). 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 atriangle-based data structureinstead of their quad-edge 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):74-123, April 1985.Available from the ACM Digital Library. 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.
• 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. 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.)
• 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, 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):387-421, 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):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.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 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).
• Jonathan Richard Shewchuk, Robust Adaptive Floating-Point Geometric Predicates, Proceedings of the Twelfth Annual Symposium on Computational Geometry, pages 141-150, 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. 132-143, 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. 163-172, 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(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. PostScript (5,348k).

Return to Triangle home page.