In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. 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. Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art.
References[edit | edit source]
- 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.
- Longley, Paul A.; Goodchild, Michael F.; Maguire, David J.; Rhind, David W. (2005). "18.104.22.168 Thiessen polygons". Geographic Information Systems and Science. Wiley. pp. 333–. ISBN 978-0-470-87001-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.
- 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. Unknown parameter
- 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.