TOPICS

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.

Art Gallery Theorem, Computational Geometry, Convex Hull, Delaunay Triangulation, Halfspace Intersection, Medial Axis, Triangulation, Voronoi Polygon

Explore with Wolfram|Alpha

More things to try:

References

Aurenhammer, F. and Klein, R. "Voronoi Diagrams." Ch. 5 in Handbook of Computational Geometry (Ed. J.-R. Sack and J. Urrutia). Amsterdam, Netherlands: North-Holland, pp. 201-290, 2000.Austin, D. "Voronoi Diagrams and a Day at the Beach." Aug. 2006. http://www.ams.org/publicoutreach/feature-column/fcarc-voronoi.Barber, C. B.; Dobkin, D. P.; and Huhdanpaa, H. T. "The Quickhull Algorithm for Convex Hulls." ACM Trans. Mathematical Software 22, 469-483, 1996.de Berg, M.; van Kreveld, M.; Overmans, M.; and Schwarzkopf, O. "Voronoi Diagrams: The Post Office Problem." Ch. 7 in Computational Geometry: Algorithms and Applications, 2nd rev. ed. Berlin: Springer-Verlag, pp. 147-163, 2000.Dirichlet, G. L. "Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen." J. reine angew. Math. 40, 209-227, 1850.Eppstein, D. "Nearest Neighbors and Voronoi Diagrams." http://www.ics.uci.edu/~eppstein/junkyard/nn.html.Field, K. "Something in the Water: The Mythology of Snow's Map of Cholera." Dec. 3, 2020. https://www.esri.com/arcgis-blog/products/arcgis-pro/mapping/something-in-the-water-the-mythology-of-snows-map-of-cholera/.The Geometry Center. "Qhull." http://www.qhull.org/.Guibas, L. and Stolfi, J. "Primitives for the Manipulation of General Subdivisions and the Computations of Voronoi Diagrams." ACM Trans. Graphics 4, 74-123, 1985.Klee, V. "On the Complexity of -Dimensional Voronoi Diagrams." Archiv. Math. 34, 75-80, 1980.Okabe, A.; Boots, B.; and Sugihara, K. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd ed. New York: Wiley, 2000.Preparata, F. R. and Shamos, M. I. Computational Geometry: An Introduction. New York: Springer-Verlag, 1985.Skiena, S. S. "Voronoi Diagrams." §8.6.4 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 358-360, 1997.Snow, J. On the Mode of Communication of Cholera. London: C. F. Cheffins, 1854.Snow, J. On the Mode of Communication of Cholera, 2nd ed. London: Churchill, 1855. http://www.ph.ucla.edu/epi/snow/snowbook.html.Snow, J. "John Snow's Map 1 (1854)." In On the Mode of Communication of Cholera. London: Churchill, 1855. http://www.ph.ucla.edu/epi/snow/snowmap1_1854_lge.htm.Voronoi, G. "Nouvelles applications des paramètres continus à la théorie des formes quadratiques." J. reine angew. Math. 133, 97-178, 1907.

Voronoi Diagram

Cite this as:

Weisstein, Eric W. "Voronoi Diagram." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/VoronoiDiagram.html