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 . 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.

convex hull | triangulation | Voronoi diagram