Voronoi diagram

20 points and their Voronoi cells (larger version below)

In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation.

The Voronoi diagram is named after mathematician Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi cells are also known as Thiessen polygons, after Alfred H. Thiessen.[1][2][3] Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art.[4][5]

  1. ^ Burrough, Peter A.; McDonnell, Rachael; McDonnell, Rachael A.; Lloyd, Christopher D. (2015). "8.11 Nearest neighbours: Thiessen (Dirichlet/Voroni) polygons". Principles of Geographical Information Systems. Oxford University Press. pp. 160–. ISBN 978-0-19-874284-5.
  2. ^ Longley, Paul A.; Goodchild, Michael F.; Maguire, David J.; Rhind, David W. (2005). "14.4.4.1 Thiessen polygons". Geographic Information Systems and Science. Wiley. pp. 333–. ISBN 978-0-470-87001-3.
  3. ^ Sen, Zekai (2016). "2.8.1 Delaney, Varoni, and Thiessen Polygons". Spatial Modeling Principles in Earth Sciences. Springer. pp. 57–. ISBN 978-3-319-41758-5.
  4. ^ Aurenhammer, Franz (1991). "Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure". ACM Computing Surveys. 23 (3): 345–405. doi:10.1145/116873.116880. S2CID 4613674.
  5. ^ Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (2000). Spatial Tessellations – Concepts and Applications of Voronoi Diagrams (2nd ed.). John Wiley. ISBN 978-0-471-98635-5.