Editing Voronoi diagram (section)

==Applications==

=== Meteorology/Hydrology ===
It is used in meteorology and engineering hydrology to find the weights for precipitation data of stations over an area (watershed). The points generating the polygons are the various station that record precipitation data. Perpendicular bisectors are drawn to the line joining any two stations. This results in the formation of polygons around the stations. The area <math>(A_i)</math> touching station point is known as influence area of the station. The average precipitation is calculated by the formula <math>\bar{P}=\frac{\sum A_i P_i}{\sum A_i}</math>{{see also|Delaunay triangulation#Applications}}

=== Humanities and social sciences===
*In [[classical archaeology]], specifically [[art history]], the symmetry of [[statue]] heads is analyzed to determine the type of statue a severed head may have belonged to. An example of this that made use of Voronoi cells was the identification of the [[Sabouroff head]], which made use of a high-resolution [[polygon mesh]].<ref name="Hoelscher20a" /><ref name="Hoelscher20b" />
*In [[dialectometry]], Voronoi cells are used to indicate a supposed linguistic continuity between survey points.
*In [[political science]], Voronoi diagrams have been used to study multi-dimensional, multi-party competition.<ref>{{cite book |last1=Laver |first1=Michael |last2=Sergenti |first2=Ernest |title=Party competition : an agent-based model |date=2012 |publisher=Princeton University Press |location=Princeton |isbn=978-0-691-13903-6}}</ref>

=== Natural sciences ===
[[File:Voronoi growth euclidean.gif|thumb|A Voronoi tessellation emerges by radial growth from seeds outward.]]
*In [[biology]], Voronoi diagrams are used to model a number of different biological structures, including [[Cell (biology)|cells]]<ref>{{cite journal |last1=Bock |first1=Martin |last2=Tyagi |first2=Amit Kumar |last3=Kreft |first3=Jan-Ulrich |last4=Alt |first4=Wolfgang |title=Generalized Voronoi Tessellation as a Model of Two-dimensional Cell Tissue Dynamics |journal=Bulletin of Mathematical Biology |volume=72 |issue=7 |pages=1696–1731 |doi=10.1007/s11538-009-9498-3 |pmid=20082148 |year=2009 |arxiv=0901.4469v1 |bibcode=2009arXiv0901.4469B |s2cid=16074264}}</ref> and [[Cancellous bone|bone microarchitecture.]]<ref>{{cite journal |author=Hui Li |editor2-first=Robert |editor2-last=Sitnik |editor1-first=Atilla M |editor1-last=Baskurt |title=Spatial Modeling of Bone Microarchitecture |journal=Three-Dimensional Image Processing (3Dip) and Applications II |volume=8290 |pages=82900P |year=2012 |bibcode=2012SPIE.8290E..0PL |doi=10.1117/12.907371 |s2cid=1505014}}</ref> Indeed, Voronoi tessellations work as a geometrical tool to understand the physical constraints that drive the organization of biological tissues.<ref name="Sanchez-Gutierrez 77–88">{{Cite journal |last1=Sanchez-Gutierrez |first1=D. |last2=Tozluoglu |first2=M. |last3=Barry |first3=J. D. |last4=Pascual |first4=A. |last5=Mao |first5=Y. |last6=Escudero |first6=L. M. |date=2016-01-04 |title=Fundamental physical cellular constraints drive self-organization of tissues |journal=The EMBO Journal |volume=35 |issue=1 |pages=77–88 |doi=10.15252/embj.201592374 |pmc=4718000 |pmid=26598531}}</ref>
*In [[hydrology]], Voronoi diagrams are used to calculate the rainfall of an area, based on a series of point measurements. In this usage, they are generally referred to as Thiessen polygons.
*In [[ecology]], Voronoi diagrams are used to study the growth patterns of forests and forest canopies, and may also be helpful in developing predictive models for forest fires.
*In [[ethology]], Voronoi diagrams are used to model domains of danger in the [[selfish herd theory]].
*In [[computational chemistry]], ligand-binding sites are transformed into Voronoi diagrams for [[machine learning]] applications (e.g., to classify binding pockets in proteins).<ref>{{cite book |last1=Feinstein |first1=Joseph |contribution=Bionoi: A Voronoi Diagram-Based Representation of Ligand-Binding Sites in Proteins for Machine Learning Applications |date=2021 |url=https://doi.org/10.1007/978-1-0716-1209-5_17 |title=Protein-Ligand Interactions and Drug Design |pages=299–312 |editor-last=Ballante |editor-first=Flavio |series=Methods in Molecular Biology |place=New York, NY |publisher=Springer US |language=en |doi=10.1007/978-1-0716-1209-5_17 |isbn=978-1-0716-1209-5 |access-date=2021-04-23 |last2=Shi |first2=Wentao |last3=Ramanujam |first3=J. |last4=Brylinski |first4=Michal |volume=2266 |pmid=33759134 |s2cid=232338911}}</ref> In other applications, Voronoi cells defined by the positions of the nuclei in a molecule are used to compute [[partial charge|atomic charge]]s. This is done using the [[Voronoi deformation density]] method.
*In [[astrophysics]], Voronoi diagrams are used to generate adaptative smoothing zones on images, adding signal fluxes on each one. The main objective of these procedures is to maintain a relatively constant [[signal-to-noise ratio]] on all the images.
*In [[computational fluid dynamics]], the Voronoi tessellation of a set of points can be used to define the computational domains used in [[finite volume]] methods, e.g. as in the moving-mesh cosmology code AREPO.<ref>{{cite journal |title=E pur si muove: Galilean-invariant cosmological hydrodynamical simulations on a moving mesh |last=Springel |first=Volker |year=2010 |journal=MNRAS |volume=401 |issue=2 |pages=791–851 |doi=10.1111/j.1365-2966.2009.15715.x |doi-access=free |bibcode=2010MNRAS.401..791S |arxiv=0901.4107 |s2cid=119241866}}</ref>
*In [[computational physics]], Voronoi diagrams are used to calculate profiles of an object with [[Shadowgraph]] and proton radiography in [[High energy density physics]].<ref>{{Cite journal |last=Kasim |first=Muhammad Firmansyah |date=2017-01-01 |title=Quantitative shadowgraphy and proton radiography for large intensity modulations |journal=Physical Review E |volume=95 |issue=2 |pages=023306 |doi=10.1103/PhysRevE.95.023306 |pmid=28297858 |arxiv=1607.04179 |bibcode=2017PhRvE..95b3306K |s2cid=13326345}}</ref>

=== Health ===
*In [[medical diagnosis]], models of muscle tissue, based on Voronoi diagrams, can be used to detect neuromuscular diseases.<ref name="Sanchez-Gutierrez 77–88"/> 
*In [[epidemiology]], Voronoi diagrams can be used to correlate sources of infections in epidemics. One of the early applications of Voronoi diagrams was implemented by [[John Snow (physician)|John Snow]] to study the [[1854 Broad Street cholera outbreak]] in Soho, England. He showed the correlation between residential areas on the map of Central London whose residents had been using a specific water pump, and the areas with the most deaths due to the outbreak.<ref name="Johnson2006">{{cite book |author=Steven Johnson |title=The Ghost Map: The Story of London's Most Terrifying Epidemic — and How It Changed Science, Cities, and the Modern World |url=https://books.google.com/books?id=8R3NrzE8veEC&pg=PT187 |date=19 October 2006 |access-date=16 October 2017 |publisher=Penguin Publishing Group |isbn=978-1-101-15853-1 |page=187}}</ref>

=== Engineering ===
*In [[polymer physics]], Voronoi diagrams can be used to represent free volumes of polymers.
*In [[materials science]], polycrystalline microstructures in metallic alloys are commonly represented using Voronoi tessellations.
*In island growth, the Voronoi diagram is used to estimate the growth rate of individual islands.<ref name="MulheranBlackman1996">{{cite journal |last1=Mulheran |first1=P. A. |last2=Blackman |first2=J. A. |title=Capture zones and scaling in homogeneous thin-film growth |journal=Physical Review B |volume=53 |issue=15 |year=1996 |pages=10261–7 |doi=10.1103/PhysRevB.53.10261 |pmid=9982595 |bibcode=1996PhRvB..5310261M}}</ref><ref name="PimpinelliTumbek2014">{{cite journal |last1=Pimpinelli |first1=Alberto |last2=Tumbek |first2=Levent |last3=Winkler |first3=Adolf |title=Scaling and Exponent Equalities in Island Nucleation: Novel Results and Application to Organic Films |journal=The Journal of Physical Chemistry Letters |volume=5 |issue=6 |year=2014 |pages=995–8 |doi=10.1021/jz500282t |pmid=24660052 |pmc=3962253}}</ref><ref name="FanfoniPlacidi2007">{{cite journal |last1=Fanfoni |first1=M. |last2=Placidi |first2=E. |last3=Arciprete |first3=F. |last4=Orsini |first4=E. |last5=Patella |first5=F. |last6=Balzarotti |first6=A. |title=Sudden nucleation versus scale invariance of InAs quantum dots on GaAs |journal=Physical Review B |volume=75 |issue=24 |pages=245312 |year=2007 |issn=1098-0121 |doi=10.1103/PhysRevB.75.245312 |bibcode=2007PhRvB..75x5312F |s2cid=120017577}}</ref><ref name="MiyamotoMoutanabbir2009">{{cite journal |last1=Miyamoto |first1=Satoru |last2=Moutanabbir |first2=Oussama |last3=Haller |first3=Eugene E. |last4=Itoh |first4=Kohei M. |title=Spatial correlation of self-assembled isotopically pure Ge/Si(001) nanoislands |journal=Physical Review B |volume=79 |issue=165415 |pages=165415 |year=2009 |issn=1098-0121 |doi=10.1103/PhysRevB.79.165415 |bibcode=2009PhRvB..79p5415M |s2cid=13719907 }}</ref><ref name="Löbl Zhai Jahn Ritzmann p. ">{{cite journal |last1=Löbl |first1=Matthias C. |last2=Zhai |first2=Liang | last3=Jahn |first3=Jan-Philipp |last4=Ritzmann |first4=Julian |last5=Huo |first5=Yongheng |last6=Wieck |first6=Andreas D. |last7=Schmidt |first7=Oliver G. |last8=Ludwig |first8=Arne |last9=Rastelli |first9=Armando |last10=Warburton |first10=Richard J. |title=Correlations between optical properties and Voronoi-cell area of quantum dots |journal=Physical Review B |volume=100 |issue=15 |date=2019-10-03 |issn=2469-9950 |doi=10.1103/physrevb.100.155402 |page=155402 |arxiv=1902.10145 |bibcode=2019PhRvB.100o5402L |s2cid=119443529}}</ref>
*In [[solid-state physics]], the [[Wigner-Seitz cell]] is the Voronoi tessellation of a solid, and the [[Brillouin zone]] is the Voronoi tessellation of reciprocal ([[wavenumber]]) space of crystals which have the symmetry of a space group.
*In [[aviation]], Voronoi diagrams are superimposed on oceanic plotting charts to identify the nearest airfield for in-flight diversion (see [[ETOPS]]), as an aircraft progresses through its flight plan.
*In [[architecture]], Voronoi patterns were the basis for the winning entry for the redevelopment of [[The Arts Centre Gold Coast]].<ref>{{cite web|title=GOLD COAST CULTURAL PRECINCT|url=http://www.a-r-m.com.au/projects_GoldCoastCP.html|publisher=ARM Architecture|access-date=2014-04-28|archive-date=2016-07-07|archive-url=https://web.archive.org/web/20160707155535/http://www.a-r-m.com.au/projects_GoldCoastCP.html|url-status=dead}}</ref>
*In [[urban planning]], Voronoi diagrams can be used to evaluate the Freight Loading Zone system.<ref>{{Cite journal |last1=Lopez |first1=C. |last2=Zhao |first2=C.-L. |last3=Magniol |first3=S |last4=Chiabaut |first4=N |last5=Leclercq |first5=L |date=28 February 2019 |title=Microscopic Simulation of Cruising for Parking of Trucks as a Measure to Manage Freight Loading Zone |journal=Sustainability |volume=11 (5), 1276|issue=5 |page=1276 |doi=10.3390/su11051276 |doi-access=free |bibcode=2019Sust...11.1276L }}</ref>
*In [[mining]], Voronoi polygons are used to estimate the reserves of valuable materials, minerals, or other resources. Exploratory drillholes are used as the set of points in the Voronoi polygons.
*In [[surface metrology]], Voronoi tessellation can be used for [[surface roughness]] modeling.<ref>{{Cite journal |last1=Singh |first1=K. |last2=Sadeghi |first2=F. |last3=Correns |first3=M. |last4=Blass |first4=T. |date=December 2019 |title=A microstructure based approach to model effects of surface roughness on tensile fatigue |url=https://www.sciencedirect.com/science/article/pii/S0142112319303330#f0005 |journal=International Journal of Fatigue |volume=129 |page=105229 |doi=10.1016/j.ijfatigue.2019.105229 |s2cid=202213370}}</ref>
*In [[robotics]], some of the control strategies and path planning algorithms<ref>{{cite journal |last1=Niu |first1=Hanlin |last2=Savvaris |first2=Al |last3=Tsourdos |first3=Antonios |last4=Ji |first4=Ze |title=Voronoi-visibility roadmap-based path planning algorithm for unmanned surface vehicles |journal=The Journal of Navigation |year=2019 |volume=72 |issue=4 |pages=850–874 |doi=10.1017/S0373463318001005|bibcode=2019JNav...72..850N |s2cid=67908628 |url=https://orca.cardiff.ac.uk/118170/1/Voronoi-Visibility%20Roadmap-based%20Path%20Planning%20Algorithm%20for%20Unmanned%20Su.._.pdf}}</ref> of [[Multi-agent system|multi-robot systems]] are based on the Voronoi partitioning of the environment.<ref>{{Cite journal |last1=Cortes |first1=J. |last2=Martinez |first2=S. |last3=Karatas |first3=T. |last4=Bullo |first4=F. |date=April 2004 |title=Coverage control for mobile sensing networks |url=https://ieeexplore.ieee.org/document/1284411 |journal=IEEE Transactions on Robotics and Automation |volume=20 |issue=2 |pages=243–255 |doi=10.1109/TRA.2004.824698 |s2cid=2022860 |issn=2374-958X}}</ref><ref>{{Cite journal |last1=Teruel |first1=Enrique |last2=Aragues |first2=Rosario |last3=López-Nicolás |first3=Gonzalo |date=April 2021|title=A Practical Method to Cover Evenly a Dynamic Region With a Swarm |url=https://ieeexplore.ieee.org/document/9349134 |journal=IEEE Robotics and Automation Letters |volume=6 |issue=2 |pages=1359–1366 |doi=10.1109/LRA.2021.3057568 |s2cid=232071627 |issn=2377-3766}}</ref>

=== Mathematics ===
*A [[point location]] data structure can be built on top of the Voronoi diagram in order to answer [[nearest neighbor search|nearest neighbor]] queries, where one wants to find the object that is closest to a given query point. Nearest neighbor queries have numerous applications. For example, one might want to find the nearest hospital or the most similar object in a [[database]]. A large application is [[vector quantization]], commonly used in [[data compression]]. 
*In [[geometry]], Voronoi diagrams can be used to find the [[Largest empty sphere|largest empty circle]] amid a set of points, and in an enclosing polygon; e.g. to build a new supermarket as far as possible from all the existing ones, lying in a certain city.
*Voronoi diagrams together with farthest-point Voronoi diagrams are used for efficient algorithms to compute the [[Roundness (object)|roundness]] of a set of points.<ref name="berg2008" /> The Voronoi approach is also put to use in the evaluation of circularity/[[roundness (object)|roundness]] while assessing the dataset from a [[coordinate-measuring machine]].
*Zeroes of iterated derivatives of a rational function on the complex plane accumulate on the edges of the Voronoi diagam of the set of the poles ([[Pólya's shires theorem]]<ref>Pólya, G. On the zeros of the derivatives of a function and its analytic character. Bulletin
of the AMS, Volume 49, Issue 3, 178-191, 1943.</ref>).

=== Informatics ===
*In [[Computer network|networking]], Voronoi diagrams can be used in derivations of the capacity of a [[wireless network]].
*In [[computer graphics]], Voronoi diagrams are used to calculate 3D shattering / fracturing geometry patterns.  It is also used to [[Procedural generation|procedurally generate]] organic or lava-looking textures.
* In autonomous [[robot navigation]], Voronoi diagrams are used to find clear routes. If the points are obstacles, then the edges of the graph will be the routes furthest from obstacles (and theoretically any collisions).
*In [[machine learning]], Voronoi diagrams are used to do [[k-nearest neighbor algorithm|1-NN]] classifications.<ref>{{cite book |title=Machine Learning |url=https://archive.org/details/machinelearning00mitc_087 |url-access=limited |first=Tom M. |last=Mitchell |year=1997 |publisher=McGraw-Hill |edition=International |isbn=978-0-07-042807-2 |page=[https://archive.org/details/machinelearning00mitc_087/page/n244 233]}}</ref>
*In global scene reconstruction, including with random sensor sites and unsteady wake flow, geophysical data, and 3D turbulence data, Voronoi tesselations are used with [[deep learning]].<ref>{{Cite web|last=Shenwai|first=Tanushree|date=2021-11-18|title=A Novel Deep Learning Technique That Rebuilds Global Fields Without Using Organized Sensor Data|url=https://www.marktechpost.com/2021/11/18/a-novel-deep-learning-technique-that-rebuilds-global-fields-without-using-organized-sensor-data/|access-date=2021-12-05 |website=MarkTechPost |language=en-US}}</ref>
*In [[user interface]] development, Voronoi patterns can be used to compute the best hover state for a given point.<ref>Archived at [https://ghostarchive.org/varchive/youtube/20211211/90NsjKvz9Ns Ghostarchive]{{cbignore}} and the [https://web.archive.org/web/20140611194118/http://www.youtube.com/watch?v=90NsjKvz9Ns&gl=US&hl=en Wayback Machine]{{cbignore}}: {{Cite web |url=https://www.youtube.com/watch?v=90NsjKvz9Ns|title=Mark DiMarco: User Interface Algorithms [JSConf2014]|date=11 June 2014 |via=www.youtube.com}}{{cbignore}}</ref>