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.
points into
are
-Dimensional Voronoi Diagrams."
Archiv. Math.
34
,
75-80, 1980.
Okabe, A.; Boots, B.; and Sugihara, K.