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.