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
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
with the option setting InterpolationOrder -> 0 (right two figures).
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.