Voronoi Diagram

A Voronoi diagram partitions a plane containing generating 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 notable historical connection is 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 1855ab). Two versions of Snow's map must be distinguished. The version in the second edition of On the Mode of Communication of Cholera shows 13 pumps (Snow 1855a). The revised version in the parish committee's report shows 14 pumps, corrects the position of the Broad Street pump, and adds a dotted boundary enclosing locations nearer to that pump by walking distance than to the other pumps (Snow 1855b, p. 109; Brody et al. 2000). Snow's map does not show a complete tessellation into pump regions. The connection is this single catchment, which essentially represents the Broad Street pump's Voronoi cell for distance along streets (Austin 2006).

The figure above shows Snow's map from the parish report on the 1854 outbreak (Snow 1855b, map between pp. 106-107). The catchment boundary is the fine dotted curve surrounding the Broad Street pump. The heavier broken outer line delimits the area in which deaths were plotted. Clicking the map opens the full-resolution historical image.

The figure above is a modern reconstruction using the 14 pumps in the revised map and digitized street and mortality data (Li). Each location first accesses its nearest mapped street line segment and is then assigned to the pump reached by the shortest path along the street network. The red outline marks the resulting Broad Street catchment. The blue dashed curve is an approximate tracing of Snow's historical boundary, aligned using the mapped pumps. The colored block interiors extrapolate this access rule, and disconnected areas without a reachable pump remain white. The black points show digitized fatalities. This is an approximate network-distance model, rather than the Euclidean distance construction in the opening definition or a record of actual pump use. Snow's account explicitly considered distance by the nearest road (Snow 1855b, p. 109).

Field (2020) emphasizes that Snow's 1849 waterborne hypothesis preceded the map, which illustrated an existing case rather than initiating that hypothesis. He notes that the epidemic was likely already declining when local officials removed the pump handle. He also explains that mapping disease cases was not an innovation of Snow's map, citing Valentine Seaman's map of yellow-fever cases in New York City (Seaman 1798, plate I) as an earlier example.

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.

Centroidal Voronoi diagrams on the sphere, in which each generating point is the geometric centroid of its cell, have been investigated (Ivanov 2026).

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.