The Delaunay Tessellation is the dual of a Voronoi diagram. Given a finite set of sites, the tessellation contains the convex hull of every subset that can lie on the boundary of a sphere with empty interior.

Usually, points are assumed to be (or perturbed to be) in general position, so that all convex hulls are simplices. Here is a 2-d demo.

Papers & 2d Delaunay triangulation code

• Leonidas J. Guibas, Jorge Stolfi: Primitives for the Manipulation of General Subdivisions and Computation of Voronoi Diagrams. ACM Transactions on Graphics 4(2): 74-123 (1985) http://doi.acm.org/10.1145/282918.282923 (Introduces and uses the quad-edge data structure; skim the first half, and read the incremental algorithm and divide & conquer algorithm that are given in full detail.)
• Dani Lischinski, Incremental Delaunay Triangulation, "Graphics Gems IV", Academic Press, 1994. (I need to scan this paper) C++ code here (An implementation of Guibas & Stolfi's quad-edge and incremental Delaunay in C++.)
• In case you want to see it, source code for my demo implementation in Java. This uses triangle-based data structure that has fewer pointers than the quad edge, but is a little harder to do the swap.
• Tripod: this point-based data structure uses the fewest pointers and has the best, but needs to be completed to an implementation. This would be worth a publication. Code & 3 page draft description.
• J. R. Shewchuk. Triangle: engineering a 2d quality mesh generator and Delaunay triangulator. In First Workshop on Applied Computational Geometry. Association for Computing Machinery, May 1996. (This is one of the most popular implementations, because it is robust yet still fast.)

3d Delaunay code

• Incremental triangulation in 3d -- designed to work well for protein data, which is evenly spaced and limited precision. Comparison paper here. bare bones C version C++ version Detailed technical paper in progress with Leo.)
• Qhull
• Pyramid

-- JackSnoeyink - 17 Feb 2005
to top