Editing Voronoi diagram (section)

{{Short description|Type of plane partition}}
[[Image:Euclidean Voronoi diagram.svg|thumb|20 points and their Voronoi cells (larger version [[#Illustration|below]])]]

In [[mathematics]], a '''Voronoi diagram''' is a [[Partition of a set|partition]] of a [[plane (geometry)|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 (mathematics)|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 [[Duality (mathematics)|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]].<ref>{{cite book |first1=Peter A. |last1=Burrough |first2=Rachael |last2=McDonnell |first3=Rachael A. |last3=McDonnell |first4=Christopher D. |last4=Lloyd |title=Principles of Geographical Information Systems |chapter=8.11 Nearest neighbours: Thiessen (Dirichlet/Voroni) polygons |chapter-url=https://books.google.com/books?id=kvoJCAAAQBAJ&pg=PA160 |year=2015 |publisher=Oxford University Press |isbn=978-0-19-874284-5 |pages=160–}}</ref><ref>{{cite book |first1=Paul A. |last1=Longley |first2=Michael F. |last2=Goodchild |first3=David J. |last3=Maguire |first4=David W. |last4=Rhind |title=Geographic Information Systems and Science |chapter=14.4.4.1 Thiessen polygons |chapter-url=https://books.google.com/books?id=-FbVI-2tSuYC&pg=PA333 |date=2005 |publisher=Wiley |isbn=978-0-470-87001-3 |pages=333–}}</ref><ref>{{cite book |first=Zekai |last=Sen |title=Spatial Modeling Principles in Earth Sciences |chapter=2.8.1 Delaney, Varoni, and Thiessen Polygons  |chapter-url=https://books.google.com/books?id=6N0yDQAAQBAJ&pg=PA57 |date=2016 |publisher=Springer |isbn=978-3-319-41758-5 |pages=57–}}</ref> Voronoi diagrams have practical and theoretical applications in many fields, mainly in [[science]] and [[technology]], but also in [[visual art]].<ref>{{cite journal |first=Franz |last=Aurenhammer |author-link=Franz Aurenhammer |date=1991 |title=Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure |journal=ACM Computing Surveys |volume=23 |issue=3 |pages=345–405 |doi=10.1145/116873.116880|s2cid=4613674 }}</ref><ref>{{cite book |first1=Atsuyuki |last1=Okabe |first2=Barry |last2=Boots |first3=Kokichi |last3=Sugihara |first4=Sung Nok |last4=Chiu |date=2000 |title=Spatial Tessellations – Concepts and Applications of Voronoi Diagrams |edition=2nd |publisher=John Wiley |isbn=978-0-471-98635-5}}</ref>