TOPICS

# 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 are dual to each other.

Convex Hull, Halfspace Intersection, Triangulation, Voronoi Diagram

## Explore with Wolfram|Alpha

More things to try:

## References

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." http://www.qhull.org/. Hinton, P. J. "qh-math: A MathLink Interface To Qhull's Delaunay Triangulation." http://library.wolfram.com/infocenter/MathSource/1160/.Lee, 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. https://mathworld.wolfram.com/DelaunayTriangulation.html