Voronoi Diagram

The partitioning of a plane with points into convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other. A Voronoi diagram is sometimes also known as a Dirichlet tessellation. The cells are called Dirichlet regions, Thiessen polytopes, or Voronoi polygons.

Voronoi diagrams were considered as early at 1644 by René Descartes and were used by Dirichlet (1850) in the investigation of positive quadratic forms. They were also studied by Voronoi (1907), who extended the investigation of Voronoi diagrams to higher dimensions. They find widespread applications in areas such as computer graphics, epidemiology, geophysics, and meteorology. A particularly notable use of a Voronoi diagram was the analysis of the 1854 cholera epidemic in London, in which physician John Snow determined a strong correlation of deaths with proximity to a particular (and infected) water pump on Broad Street (Snow 1854, Snow 1855). In his analysis, Snow constructed a map on which he drew a line labeled "Boundary of equal distance between Broad Street Pump and other Pumps." This line essentially indicated the Broad Street Pump's Voronoi cell (Austin 2006). However, for an analysis highlighting some of the oversimplifications and misattributions in this folklore history account of the events surrounding Snow and the London cholera incident, see Field (2020).

The Wolfram Language command VoronoiDiagram[pts] in the Wolfram Language package ComputationalGeometry` returns a data structure corresponding to the Voronoi diagram of a given set of points, and DiagramPlot[pts] gives a graphical illustration of the Voronoi diagram (left figure above). Voronoi diagrams can be even more easily visualized in the Wolfram Language using graphics functions such as ListDensityPlot and ListPlot3D with the option setting InterpolationOrder -> 0 (right two figures).

The Delaunay triangulation and Voronoi diagram in are dual to each other in the graph theoretical sense.

In Season 4 episode "Black Swan" of the television crime drama NUMB3RS, math genius Charles Eppes proposes performing a time series analysis of overlapping Dirichlet tessellations in an attempt to track the movements of a suspect.