Delaunay Triangulation


The Delaunay triangulation is a triangulation which is equivalent to the nerve of the cells in a Voronoi diagram, i.e., that triangulation of the convex hull of the points in the diagram in which every circumcircle of a triangle is an empty circle (Okabe et al. 1992, p. 94).

The Wolfram Language command PlanarGraphPlot[pts] in the Wolfram Language package ComputationalGeometry` plots the Delaunay triangulation of the given list of points. Qhull may be used to compute these structures efficiently.

The Delaunay triangulation and Voronoi diagram in R^2 are dual to each other.

See also

Convex Hull, Halfspace Intersection, Triangulation, Voronoi Diagram

Explore with Wolfram|Alpha


Barber, C. B.; Dobkin, D. P.; and Huhdanpaa, H. T. "The Quickhull Algorithm for Convex Hulls." ACM Trans. Mathematical Software 22, 469-483, 1996.The Geometry Center. "Qhull." Hinton, P. J. "qh-math: A MathLink Interface To Qhull's Delaunay Triangulation.", D. T. and Schachter, B. J. "Two Algorithms for Constructing a Delaunay Triangulation." Int. J. Computer Information Sci. 9, 219-242, 1980.Okabe, A.; Boots, B.; and Sugihara, K. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. New York: Wiley, 1992.Preparata, F. R. and Shamos, M. I. Computational Geometry: An Introduction. New York: Springer-Verlag, 1985.

Referenced on Wolfram|Alpha

Delaunay Triangulation

Cite this as:

Weisstein, Eric W. "Delaunay Triangulation." From MathWorld--A Wolfram Web Resource.

Subject classifications