Ogled vira Voronojev diagram

{{short description|Vrsta particije ravnine}}
[[slika:Euclidean Voronoi diagram.svg|thumb|right|20 naključnih [[točka (geometrija)|točk]] v [[ravnina|ravnini]] in njihove Voronojeve celice (večja različica [[#Ilustracija|spodaj]])]]
[[slika:Thiessen Polygons.png|thumb|right|Thiessnovi mnogokotniki]]
[[slika:Voronoi on neurons.jpg|thumb|right|Fotografija [[nevron]]ov (levo) in ustrezni Voronojev mozaik, zgrajen na podlagi njihovih [[centroid]]ov (geometrijskih središč)]]
'''Voronojev diagrám''' [voronójev ~] je v [[matematika|matematiki]] [[particija množice|razdeljevanje]] [[ravnina|ravnine]] na področja, ki so blizu vsakemu od dane množice objektov. V najpreprostejšem primeru so ti objekti samo končno število [[točka (geometrija)|točk]] v ravnini (imenovanih semena, mesta ali generatorji). Za vsako seme obstaja ustrezno področje, imenovano '''Voronojeva celica''', sestavljena iz vseh točk ravnine, ki so bližje temu semenu kot kateri koli drugi. Voronojev diagram množice točk v [[dvorazsežni prostor|dveh razsežnostih]] je [[dualnost (matematika)|dualen]] svoji ustrezni [[Delaunayeva triangulacija|Delaunayevi triangulaciji]] v smislu [[teorija grafov|teorije grafov]].

Voronojev diagram se imenuje po ruskem matematiku [[Georgij Feodosjevič Voronoj|Georgiju Feodosjeviču Voronoju]], ki jih je leta [[1908 v znanosti|1908]] definiral in raziskoval splošni ''n''-razsežni primer.{{r|voro_1908}} Imenuje se tudi '''Voronojeva teselacija''' (~ '''pokritje''', ~ '''tlakovanje'''), '''Voronojeva dekompozicija''', '''Voronojeva particija''' ali '''Dirichletova teselacija''' (po [[Johann Peter Gustav Lejeune Dirichlet|Johannu Petru Gustavu Lejeunu Dirichletu]]).{{r|burr_2015}}{{r|long_2005}}{{r|sen__2016}}{{r|diri_1850}} Voronojeve celice so znane tudi kot '''Thiessnovi mnogokotniki''', še posebej v [[vede o Zemlji|znanostih o Zemlji]] ([[geofizika|geofiziki]], [[meteorologija|meteorologiji]] in [[klimatologija|klimatologiji]]). Imenujejo se po ameriškem meteorologu [[Alfred Henry Thiessen|Alfredu Henryju Thiessnu]].{{r|thie_1911}}  Voronojevi diagrami se praktično in teoretično uporabljajo na številnih področjih, predvsem v [[znanost]]i in [[tehnologija|tehnologiji]], pa tudi v [[likovna umetnost|likovni umetnosti]].{{r|aure_1991}}{{r|okab_2000}}

== Najpreprostejši primer ==

V najpreprostejšem primeru, prikazanem na prvi sliki, je končna množica točk <math> \{p_{1}, \ldots, p_{n} \} \!\, </math> v [[evklidska ravnina|evklidski ravnini]]. V tem primeru je vsako mesto <math> p_{k} \!\, </math> preprosto točka in njena ustrezna Voronojeva celica <math> R_{k} \!\, </math> je sestavljena iz vsake točke v evklidski ravnini, katere [[razdalja]] do točke <math> p_{k} \!\, </math> je manjša ali enaka njeni razdalji do katere koli druge točke <math> p_{k} \!\, </math>. Vsaka taka celica je pridobljena iz [[presečišče|presečišča]] [[polprostor]]ov in je torej ([[konveksni politop|konveksni]]) [[polieder]].{{r|boyd_2004}} [[daljica|Daljice]], (v tem primeru [[stranica|stranice]] nastalih [[mnogokotnik]]ov), Voronojevega diagrama so vse točke v ravnini, ki so enako oddaljene od dveh najbližjih mest. Voronojeva oglišča ([[točka (teorija grafov)|vozlišča]]) so točke, ki so enako oddaljene od treh (ali več) mest.

== Formalna definicija ==

Naj je <math display="inline"> X \!\, </math> [[metrični prostor]] s funkcijo razdalje <math display="inline"> d \!\, </math>. <math display="inline"> K \!\, </math> naj je množica indeksov in <math display="inline"> (P_k)_{k \in K} \!\, </math> [[n-terica]] ([[urejeni par|urejena]] zbirka) nepraznih [[podmnožica|podmnožic]] (mest) v prostoru <math display="inline"> X \!\, </math>. Voronojeva celica ali Voronojevo območje <math display="inline"> R_{k} \!\, </math>, povezano z mestom <math display="inline"> P_{k} \!\, </math> je množica vseh točk v <math display="inline"> X \!\, </math>, katerih razdalja do <math display="inline"> P_{k} \!\, </math> ni večja od njihove razdalje do drugih mest <math display="inline"> P_{j} \!\, </math>, kjer je <math display="inline"> j \!\, </math> poljubni indeks, različen od <math display="inline"> k \!\, </math>. Z drugimi besedami, če <math display="inline"> d(x,\, A) = \inf\{d(x,\, a) \mid a \in A\} \!\, </math> označuje razdaljo med točko <math display="inline"> x \!\, </math> in podmnožico <math display="inline"> A \!\, </math>, potem velja:

: <math> R_{k} = \{x \in X \mid d(x, P_{k}) \leq d(x, P_j)\; \text{za vse} \; j \neq k\} \!\, . </math>

Voronojev diagram je preprosto trojica celic <math display="inline"> (R_{k})_{k \in K} \!\, </math>. Načeloma se lahko nekatera mesta sekajo ali celo sovpadajo (spodaj je opisana aplikacija za mesta, ki predstavljajo trgovine), vendar se običajno domneva, da so nepovezana. Poleg tega je v definiciji dovoljenih neskončno veliko mest (ta nastavitev se uporablja v [[geometrija števil|geometriji števil]] in [[kristalografija|kristalografiji]]), vendar je v mnogih primerih upoštevanih le končno veliko mest.

V posebnem primeru, ko je prostor [[razsežnost (vektorski prostor)|končnorazsežni]] [[evklidski prostor]], je vsako mesto točka, obstaja končno mnogo točk in vse so različne, potem so Voronojeve celice [[konveksni politop]]i in jih je mogoče predstaviti na kombinatorni način z njihovimi oglišči, stranicami, dvorazsežnimi ploskvami itd. Včasih se nastala kombinatorna struktura imenuje Voronojev diagram. V splošnem pa Voronojeve celice niso nujno konveksne ali celo povezane.

V običajnem evklidskem prostoru se lahko formalna definicija prepiše z običajnimi izrazi. Vsak Voronojev mnogokotnik <math display="inline"> R_{k} \!\, </math> je povezan z generatorsko točko <math display="inline"> P_{k} \!\, </math>. Naj je <math display="inline"> X </math> množica vseh točk v evklidskem prostoru. <math display="inline"> P_{1} </math> naj je točka, ki generira Voronojevo območje <math display="inline"> R_{1} \!\, </math>, <math display="inline"> P_{2} \!\, </math>, ki genrira <math display="inline"> R_{2} \!\, </math> in <math display="inline"> P_{3} \!\, </math>, ki generira <math display="inline"> R_{3} \!\, </math> in tako naprej. <!--Potem velja:

: <math> R_1 = \{x \in X \mid d(x, P_1) \leq d(x, P_2) \;\and\; d(x, P_1) \leq d(x, P_3) \;\and\; \ldots\}</math>
: <math> R_2 = \{x \in X \mid d(x, P_2) \leq d(x, P_1) \;\and\; d(x, P_2) \leq d(x, P_3) \;\and\; \ldots\}</math>
:...
--> Potem, kot je navedeno v Tran; Tainar; Safar (2009){{r|tran_2009}}, so »vse lege v Voronojevem mnogokotniku bližje generatorski točki tega mnogokotnika kot katera koli druga generatorska točka v Voronojevem diagramu v evklidski ravnini.«

== Ponazoritev ==

V preprosti ponazoritvi naj obstaja skupina trgovin v mestu. Želi se oceniti število strank za dano trgovino. Pri vseh drugih enakih pogojih (cena, izdelki, kakovost storitev itd.) je razumno domnevati, da se stranke za svojo najljubšo trgovino odločijo zgolj glede na razdaljo – šle bodo v trgovino, ki je njim najbližja. V tem primeru se lahko Voronojevo celico <math display="inline"> R_{k} \!\, </math> dane trgovine <math display="inline"> P_{k} \!\, </math> uporabi za grobo oceno števila potencialnih strank, ki obiskujejo to trgovino (ki je modelirana s točko v takšnem mestu).

Za večino mest se lahko razdalja med točkami izmeri z znano [[evklidska razdalja|evklidsko razdaljo]]:

: <math> \ell_2 = d \left[ \left( a_{1}, a_{2} \right), \left( b_{1}, b_{2} \right) \right] = \sqrt{ \left( a_{1} - b_{1} \right)^{2} + \left( a_{2} - b_{2} \right)^{2}} \!\, </math>

ali z [[geometrija taksija|manhattansko razdaljo]]:

: <math> d \left[ \left( a_{1}, a_{2} \right), \left( b_{1}, b_{2} \right) \right] = \left| a_{1} - b_{1} \right| + \left| a_{2} - b_{2} \right| \!\, . </math>

Odgovarjajoča Voronojeva diagrama izgledata različno za različno [[metrika|metriko]] razdalje.

{{več slik
 | align     = center
 | direction = horizontal
 | width     = 250
 | header    = Voronojeva diagrama na 20-ih točkah za dve različni [[metrika|metriki]]
 | header_align = center
 | image1    = Euclidean Voronoi diagram.svg
 | alt1      = Voronojev diagram za evklidsko razdaljo
 | caption1  = [[evklidska razdalja]]
 | image2    = Manhattan Voronoi Diagram.svg
 | alt2      = Voronojev diagram za manhattansko razdaljo
 | caption2  = [[manhattanska razdalja]]
}}

== Značilnosti ==

* [[dualni graf]] za Voronojev diagram (v primeru [[evklidski prostor|evklidskega prostora]] s točkovnimi mesti) odgovarja [[Delaunayeva triangulacija|Delaunayevi triangulaciji]] za isto množico točk.
* [[problem najbližjega para točk|najbližji par točk]] odgovarja dvema sosednjima celicama v Voronojevem diagramu.
* predpostavi se, da je nastavitev [[evklidska ravnina]] in da je podana diskretna množica točk. Potem sta dve točki množice sosednji na [[konveksna ogrinjača|konveksni ogrinjači]], če in samo če si njune Voronojeve celice delijo neskončno dolgo stranico.
* če je prostor [[normirani vektorski prostor|normiran]] in je razdalja do vsakega mesta dosežena (na primer ko je mesto [[kompaktna množica]] ali zaprta krogla), potem se lahko vsako Voronojevo celico predstavi kot zvezo daljic, ki izhajajo iz mest.{{r|reem_2009}} Kot je prikazano tam, ni nujno, da ta značilnost velja, ko razdalja ni dosežena.
* pod razmeroma splošnimi pogoji (prostor je morda neskončnorazsežen [[uniformno konveksni prostor|uniformno konveksen]] – lahko je neskončno mnogo mest splošne oblike itd.) imajo Voronojeve celice določeno značilnost stabilnosti – majhna sprememba v oblikah mest, na primer sprememba, ki jo povzroči translacija ali popačenje, povzroči majhno spremembo v obliki Voronojevih celic. To je geometrijska stabilnost Voronojevih diagramov.{{r|reem_2011}} Kot je prikazano tam, ta značilnost na splošno ne velja, tudi če je prostor [[dvorazsežni prostor|dvorazsežen]] (vendar neuniformno konveksen in zlasti [[neevklidska geometrija|neevklidski]]) in so mesta točke.

== Zgodovina in raziskovanje ==

Neformalno rabo Voronojevih diagramov se lahko najde pri [[René Descartes|Renéju Descartesu]] leta 1644. [[Johann Peter Gustav Lejeune Dirichlet]] je uporabil dvorazsežne in trirazsežne Voronojeve diagrame pri svojem raziskovanju [[kvadratna forma|kvadratnih form]] leta 1850. Angleški zdravnik [[John Snow]] je uporabljal diagram, podoben Voronojevemu, leta 1854 za ponazoritev kako je večina ljudi, ki je umrla zaradi [[izbruh kolere na Broad Street leta 1854|izbruha kolere na Broad Street]] v londonski četrti [[Soho]], živela bližje od okužene črpalke na Broad Street kot od katere druge črpalke.

Voronojevi diagrami se imenujejo po [[Georgij Feodosjevič Voronoj|Georgiju Feodosjeviču Voronoju]], ki je definiral in raziskoval splošni ''n''-razsežni primer leta 1908.{{r|voro_1908}} Voronojevi diagrami, ki se uporabljajo v geofiziki in meteorologiji za analizo prostorsko porazdeljenih podatkov (na primer [[merjenje]] [[padavine|padavin]]), se imenujejo po ameriškem meteorologu [[Alfred Henry Thiessen|Alfredu Henryju Thiessnu]]. V kristalografiji in [[fizika kondenzirane snovi|fiziki kondenzirane snovi]] so takšna pokritja znana tudi kot [[Wigner-Seitzeva celica|Wigner-Seitzeve celice]].

Druga enakovredna imena za ta koncept (ali njegove posebne pomembne primere) so: Voronojevi poliedri, Voronojevi mnogokotniki, domena(e) vpliva, Voronojeva dekompozicija, Voronojeva(e) teselacija(e), Dirichletova(e) teselacija(e).

== Zgledi ==
[[slika:Coloured Voronoi 3D slice.svg|thumb|right|To je rezina Voronojevega diagrama za naključno množico točk v trirazsežni [[kocka|kocki]]. V splošnem presek trirazsežnega Voronojevega pokritja ni dvorazsežno Voronojevo pokritje sámo. (Celice so vse [[konveksna množica|konveksni]] [[polieder|poliedri]].)]]

Voronojevo pokritje pravilnih [[mreža (grupa)|mrež]] točk v dveh ali treh razsežnostih da mnogo znanih [[teselacija|pokritij]].
* dvorazsežna mreža točk da nepravilno pokritje satovja z enakimi [[šestkotnik]]i s [[točkovna simetrija|točkovno simetrijo]]. V primeru pravilne trikotniške mreže točk je [[šestkotno tlakovanje|pokritje]] [[pravilno tlakovanje|pravilno]] – Voronojeve celice so pravilni šestkotniki. V primeru [[pravokotnik|pravokotniške]] mreže točk se šestkotniki skrčijo v pravokotnike v vrsticah in stolpcih. [[kvadrat (geometrija)|Kvadratna]] mreža točk da pravilno pokritje kvadratov. Pravokotniki in kvadrati se lahko pridobijo tudi z drugimi mrežami točk – na primer mreža točk, definirana z vektorjema (1, 0) in (1/2, 1/2) da kvadrate). V primeru šestkotniške mreže točk Voronojeve celice dajo [[trikotno tlakovanje|trikotniško pokritje]].
* [[enostavna kubična mreža]] da [[kubično satovje]].
* [[tesno pakiranje enakih sfer|šestkotniška tesno pakirana]] mreža da pokritje prostora s [[trapezorombski dodekaeder|trapezorombskimi dodekaedri]].
* [[ploskovno centrirana kubična mreža]] da pokritje prostora z [[rombski dodekaeder|rombskimi dodekaedri]].
* [[telesno centrirana kubična mreža]] da pokritje prostora s [[prisekani oktaeder|prisekanimi oktaedri]].
* vzporedne ravnine z enostavnimi trikotniškimi mrežami, poravnanimi druga z drugo s središči, da [[šestkotniško prizmatično satovje]].
* določene telesno centrirane štirikotniške mreže dajejo pokritje prostora z [[rombo-šeststrani dodekaeder|rombo-šestskotniškimi dodekaedri]].

Za množico točk <math display="inline"> (x, y) \!\,  </math> z <math display="inline"> x \!\, </math> v [[diskretna množica|diskretni množici]] <math display="inline"> X \!\, </math> in <math display="inline"> y \!\, </math> v diskretni množici <math display="inline"> Y \!\, </math> se dobi pravokotne ploščice s točkami, ki niso nujno v njihovih središčih.

== Voronojevi diagrami višjih redov ==

Čeprav je normalna Voronojeva celica definirana kot množica točk, najbližjih eni točki v množici <math display="inline"> S \!\, </math>, je Voronojeva celica ''n''-tega reda definirana kot množica točk, ki ima določeno množico ''n'' točk v <math display="inline"> S \!\, </math> kot svojih ''n'' najbližjih sosedov. Voronojevi diagrami višjega reda prav tako delijo prostor.

Voronojevi diagrami višjega reda se lahko generirajo rekurzivno. Za generiranje Voronojevega diagrama ''n''-tega reda iz množice <math display="inline"> S \!\, </math> se začne z diagramom reda <math display="inline"> n - 1 \!\, </math> in vsaka celica, generirana z <math display="inline"> X = \{ x_{1}, x_{2}, \ldots, x_{n-1} \} \!\, </math>, se zamenja z Voronojevim diagramom, generiranim na množici <math display="inline"> S - X\!\, </math>.

=== Voronojev diagram najoddaljenejše točke ===

Za dano množico ''n'' točk se Voronojev diagram reda <math display="inline"> n - 1 \!\, </math> imenuje Voronojev diagram najoddaljenejše točke.

Za dano množico točk <math display="inline"> S = \{ p_{1}, p_{2}, \ldots, p_{n} \} \!\, </math> Voronojev diagram najoddaljenejše točke deli ravnino na celice v katerih je ista točka <math display="inline"> P \!\, </math> najoddaljenejša točka. Točka <math display="inline"> P \!\, </math> ima celico v Voronojevem diagramu najoddaljenejše točke, če in samo če je oglišče [[konveksna ogrinjača|konveksne ogrinjače]] <math display="inline"> P \!\, </math>. Naj bo <math display="inline"> H = \{ h_{1}, h_{2}, \ldots, h_{k} \} \!\, </math> konveksna ogrinjača <math display="inline"> P \!\, </math>. Potem je Voronojev diagram najoddaljenejše točke podrazdelitev ravnine na <math display="inline"> k \!\, </math> celic, po eno za vsako točko v <math display="inline"> H \!\, </math> z značilnostjo, da točka <math display="inline"> q \!\, </math> leži v celici, ki ustreza mestu <math display="inline"> h_{i} \!\, </math>, če in samo če velja <math display="inline"> d(q, h_{i}) > d(q, p_{j}) \!\, </math> za vsako točko <math display="inline"> p_{j} \in S \!\, </math> s <math display="inline"> h_{i} \ne p_{j} \!\, </math>, kjer je <math display="inline"> d(p, q) \!\, </math> [[evklidska razdalja]] med dvema točkama <math display="inline"> p \!\, </math> in <math display="inline"> q \!\, </math>.{{r|berg_2008}}{{r|skyu_1991}}

Meje celic v Voronojevem diagramu najoddaljenejše točke imajo strukturo [[realno drevo|topološkega drevesa]] z neskončnimi [[poltrak]]ovi kot listi. Vsako končno [[drevo (teorija grafov)|drevo]] je [[izomorfizem grafov|izomorfno]] drevesu, oblikovanemu na ta način iz Voronojevega diagrama najoddaljenejše točke.{{r|bied_2016}}

== Posplošitve in variacije ==

Kot nakazuje definicija, je Voronojeve celice mogoče definirati za metrike, ki niso evklidske, kot sta na primer [[Mahalanobisova razdalja]] ali [[manhattanska razdalja]]. Vendar pa so lahko v teh primerih meje Voronojevih celic bolj zapletene kot v evklidskem primeru, saj ekvidistančno [[geometrijsko mesto točk]] za dve točki morda ne bo podprostor sorazsežnosti 1, tudi v dvorazsežnem primeru.

[[slika:Approximate Voronoi Diagram.svg|thumb|right|[[Približni Voronojev diagram]] za množico točk. Vidne so mešane barve na mehki meji Voronojevih celic.]]
V [[uteženi Voronojev diagram|uteženem Voronojevem diagramu]] je funkcija para točk, ki definira Voronojevo celico, funkcija razdalje, spremenjena z multiplikativnimi ali aditivnimi utežmi, dodeljenimi generatorskim točkam. V nasprotju s primerom Voronojevih celic, definiranih z uporabo razdalje, ki je [[metrični prostor|metrika]], so lahko v tem primeru nekatere Voronojeve celice [[prazna množica|prazne]]. [[Močnostni diagram]] je vrsta Voronojevega diagrama, definiranega iz množice [[krožnica|krožnic]] z uporabo [[izrek o tetivah|potenčne razdalje]] – lahko se ga predstavlja tudi kot uteženi Voronojev diagram, v katerem je utež, definirana iz polmera vsake krožnice, dodana [[kvadrat evklidske ravnine|kvadratu evklidske razdalje]] od središča krožnice.{{r|edel_2012}}

Voronojev diagram ''n'' točk v ''d''-razsežnem prostoru ima lahko <math display=inline>O(n^{\lceil d/2 \rceil})</math> oglišč, ki zahtevajo enako mejo za količino pomnilnika, potrebnega za shranjevanje njenega eksplicitnega opisa. Zato Voronojevi diagrami pogosto niso izvedljivi za zmerne ali višje razsežnosti. Prostorsko učinkovitejša alternativa je uporaba [[približni Voronojev diagram|približnih Voronojevih diagramov]].{{r|arya_2002}}

Voronojevi diagrami so povezani tudi z drugimi geometrijskimi strukturami, kot so na primer [[srednja os]] (ki je našla aplikacije v [[slikovna segmentacija|slikovni segmentaciji]], [[optično prepoznavanje znakov|optičnem prepoznavanju znakov]] in drugih računalniških aplikacijah), [[ravni skelet]] in [[conski diagram]]i.

== Uporabe ==

=== Meteorologija in hidrologija ===

Uporablja se v [[meteorologija|meteorologiji]] in tehniški [[hidrologija|hidrologiji]] za iskanje uteži podatkov o padavinah postaj na območju ([[razvodje|razvodju]]). Točke, ki generirajo mnogokotnike, so različne postaje, ki beležijo podatke o padavinah. Na črto, ki povezuje katerikoli dve postaji, so narisane pravokotne simetrale. Posledica tega je oblikovanje mnogokotnikov okrog postaj. Območje <math display="inline"> (A_{i}) \!\, </math>, ki se dotika točke postaje, je znano kot vplivno območje postaje. Povprečno količino padavin se izračuna po formuli <math display="inline"> \bar{P}=\frac{\sum A_{i} P_{i}}{\sum A_{i}} \!\, </math>{{glej tudi|Delaunayeva triangulacija#Uporabe}}

=== Humanistika ===

* v [[klasična arheologija|klasični arheologiji]] in še posebej v [[umetnostna zgodovina|umetnostni zgodovini]] se [[simetrija]] glav [[kip]]ov analizira za določitev kateri vrsti kipa bi lahko pripadala odrezana glava. Zgled tega, pri katerem so bile uporabljene Voronojeve celice, je bila identifikacija [[glava Saburova|glave Saburova]], ki je uporabila visokoločljivo [[mnogokotniška mreža|mnogokotniško mrežo]].{{r|hoel_2020}}{{r|baye_2020}}
* v [[dialektometrija|dialektometriji]] se Voronojeve celice rabijo za prikaz domnevne jezikovne kontinuitete med merilnimi točkami.

=== Naravoslovje  ===
[[slika:Voronoi growth euclidean.gif|thumb|right|Voronojevo pokritje nastane z radialno rastjo iz semena navzven.]]

* v [[biologija|biologiji]] se Voronojevi diagrami rabijo za modeliranje mnogih različnih bioloških struktur, kot so na primer [[celica|celice]]{{r|bock_2009}} in mikroarhitektura [[kost]]i.{{r|hui__2012}} Voronojeva pokritja dejansko delujejo kot geometrijsko orodje za razumevanje fizičnih omejitev, ki poganjajo organizacijo bioloških tkiv.{{r|sanc_2016}}
* v [[hidrologija|hidrologiji]] se Voronojevi diagrami rabijo za izračun količine [[padavine|padavin]] na območju na podlagi niza točkovnih meritev. V tej uporabi se na splošno imenujejo Thiessnovi mnogokotniki.
* v [[ekologija|ekologiji]] se Voronojevi diagrami rabijo za preučevanje vzorcev rasti [[gozd]]ov in gozdnih krošenj, lahko pa so tudi v pomoč pri razvoju napovednih modelov za gozdne [[požar]]e.
* v [[računska kemija|računski kemiji]] se mesta za vezavo ligandov pretvorijo v Voronojeve diagrame za aplikacije [[strojno učenje|strojnega učenja]] (na primer za razvrščanje veznih žepov v [[protein]]ih).{{r|fein_2021}} V drugih aplikacijah se Voronojeve celice, definirane z legami [[atomsko jedro|jeder]] v [[molekula|molekuli]], rabijo za izračun [[delni naboj|atomskih nabojev]]. To se naredi z metodo [[Voronojeva gostota deformacije|Voronojeve gostote deformacije]].
* v [[astrofizika|astrofiziki]] se Voronojevi diagrami rabijo za generiranje prilagodljivih gladilnih območij na slikah, pri čemer vsaki dodajo signalne tokove. Glavni cilj teh postopkov je ohranjanje razmeroma konstantnega [[razmerje signal-šum|razmerja med signalom in šumom]] na vseh slikah.
* v [[numerična dinamika tekočin|računski dinamiki tekočin]] se lahko Voronojevo pokritje množice točk uporabi za določitev računskih domen za uporabo v [[metoda končnih prostornin|metodah končnih prostornin]], na primer kot v kodi kozmologije premikajoče se mreže AREPO.{{r|spri_2010}}
* v [[računalniška fizika|računalniški fiziki]] se Voronojevi diagrami uporabljajo za izračun profilov telesa s [[senčni graf|senčnim grafom]] in [[proton]]sko radiografijo v [[fizika visokih gostot energije|fiziki visokih gostot energije]].{{r|kasi_2017}}

=== Zdravje ===

* v [[diagnoza|medicinski]] [[diagnostika|diagnostiki]] se lahko uporabijo modeli mišičnih tkiv na podlagi Voronojevih diagramov za zaznavo nevromuskulaturnih bolezni.{{r|sanc_2016}}
* v [[epidemiologija|epidemiologiji]] se Voronojevi diagrami lahko uporabljajo za korelacijo vzorcev okužb v [[epidemija]]h. Voronojeve diagrame je med prvimi izvedel angleški zdravnik [[John Snow]] za raziskovanje [[izbruh kolere na Broad Street leta 1854|izbruha kolere na Broad Street leta 1854]] v londonski četrti Soho. Pokazal je soodnosnost med stanovanjskimi območji na zemljevidu osrednjega Londona, kjer so stanovalci uporabljali določeno vodno črpalko, in območji z največ [[smrt]]mi zaradi izbruha.{{r|john_2006}}

=== Inženirstvo ===

* v [[fizika polimerov|fiziki polimerov]] se lahko Voronojevi diagrami uporabljajo za prikaz prostih prostornin [[polimer]]ov.
* v [[znanost o materialih|znanosti o materialih]] so [[polikristal]]inske mikrostrukture v [[kovina|kovinskih]] [[zlitina]]h običajno predstavljene s pomočjo Voronojevih pokritij. Pri rasti otokov se za oceno stopnje rasti posameznih otokov uporablja Voronojev diagram.{{r|mulh_1996}}{{r|pimp_2014}}{{r|fanf_2007}}{{r|miya_2009}}{{r|loeb_2019}} V [[fizika kondenzirane snovi|fiziki kondenzirane snovi]] je [[Wigner-Seitzeva celica]] Voronojevo pokritje [[trdnina|trdnine]], [[Brillouinova cona]] pa Voronojevo pokritje vzajemnega prostora kristalov, ki imajo simetrijo [[prostorska skupina|prostorske skupine]] ([[valovno število]]).
* v [[letalstvo|letalstvu]] se Voronojevi diagrami prekrijejo z oceanskimi grafikoni za identifikacijo najbližjega letališča za preusmeritev med letom (glej [[ETOPS]]), ko letalo napreduje skozi svoj načrt leta.
* v [[arhitektura|arhutekturi]] so uporabili Voronojeve vzorce kot osnovo za zmagovalni vnos prenove kulturnega predela [[The Arts Center Gold Coast|The Arts Center]] v [[Gold Coast, Queensland|Gold Coastu]], [[Queensland]], [[Avstralija]].{{r|spl0}}
* v [[urbanistično načrtovanje|urbanističnem načrtovanju]] se lahko Voronojevi diagrami uporabijo za ovrednotenje sistema Freight Loading Zone (''območja nakladanja tovora'').{{r|lope_2019}}
* v [[rudarstvo|rudarstvu]] je Voronojevi mnogokotniki uporabljajo za ocenitev zalog dragocenih materialov, mineralov ali drugih virov. Raziskovalne vrtine se uporabljajo kot množice točk v Voronojevih mnogokotnikih.
* v [[ploskovna metrologija|ploskovni metrologiji]] se lahko Voronojevo pokritje uporabi za modeliranje [[hrapavost površine|hrapavosti površin]].{{r|sing_2019}}
* v [[robotika|robotiki]] nekatere strategije nadzora in algoritmi za načrtovanje poti sistemov z [[mnogoagentski sistem|več]] [[robot]]i{{r|niu__2019}} temeljijo na Voronojevem razdeljevanju okolja.{{r|cort_2004}}{{r|teru_2021}}

=== Geometrija ===

* [[podatkovna struktura|podatkovno strukturo]] [[lega točke|lege točke]] se lahko zgradi prek Voronojevega diagrama za odgovor na poizvedbe [[iskanje najbližjega soseda|najbližjega soseda]], kjer se želi najti objekt, ki je najbližje dani točki poizvedbe. Poizvedbe najbližjega soseda imajo številne uporabe. Nekdo bi na primer morda želel najti najbližjo bolnišnico ali najbolj podoben objekt v [[podatkovna zbirka|podatkovni zbirki]]. Velika uporaba je [[vektorska kvantizacija]], ki se pogosto uporablja pri [[stiskanje podatkov|stiskanju podatkov]].
* v [[geometrija|geometriji]] se lahko Voronojevi diagrami uporabijo za iskanje [[največja prazna sfera|največje prazne krožnice]] sredi množice točk in v ograjenem mnogokotniku –  na primer zgraditi nov supermarket čim dlje od vseh obstoječih, ki ležijo v določenem mestu.
* Voronojevi diagrami skupaj z Voronojevimi diagrami najoddaljenejše točke se uporabljajo za učinkovite algoritme za izračun okroglosti mnmožice točk.{{r|berg_2008}} Voronojev pristop se uporablja tudi pri vrednotenju [[krožnost]]i/[[okroglost]]i pri ocenjevanju nabora podatkov iz [[koordinatni merilni stroj|koordinatnega merilnega stroja]].

=== Informatika ===

* v [[računalniško omrežje|računalniškem omrežju]] se lahko Voronojeve diagrame uporabi pri izpeljavah zmogljivosti [[brezžično omrežje|brezžičnega omrežja]].
* v [[računalniška grafika|računalniški grafiki]] se Voronojevi diagrami uporabljajo za izračun trirazsežnih geometrijskih vzorcev drobljenja in lomljenja. Uporabljajo se tudi za [[proceduralna generacija|proceduralno ustvarjanje]] organskih ali [[lava]]stih tekstur.
* v neodvisni [[robotska navigacija|robotski navigaciji]] se Voronojevi diagrami uporabljajo za iskanje jasnih [[pot]]i. Če so točke ovire, bodo [[povezava (teorija grafov)|povezave]] [[graf (matematika)|grafa]] poti, ki so najbolj oddaljene od ovir (in teoretično morebitnih trkov).
* pri [[strojno učenje|strojnem učenju]] se Voronojevi diagrami uporabljajo za razvrščanje [[algoritem k najbližjih sosedov|1-NN]].{{r|mitc_1997}}
* pri rekonstrukciji globalnih prizorov, vključno z naključnimi zaznavalnimi mesti in nestalnim pretokom, geofizikalnimi podatki in podatki o trirazsežnih turbulencah, se Voronojeva pokritja uporabljajo z [[globoko učenje|globokim učenjem]]{{r|shen_2021}}
* pri razvoju [[uporabniški vmesnik|uporabniških vmesnikov]] je mogoče Voronojeve vzorce uporabiti za izračun najboljšega stanja lebdenja za dano točko.{{r|spl1}}

=== Nauk o državi in načrtovanje ===

* V [[Melbourne|Melbournu]] so učenci državnih šol vedno upravičeni do obiskovanja osnovne šole ali srednje šole, ki je najbližja kraju njihovega bivanja, merjeno z razdaljo na premici. Zemljevid takšnih šolskih con je torej Voronojev diagram.{{r|spl2}}

=== Pekarstvo ===

* ukrajinska slaščičarka [[Dinara Kasko]] uporablja matematična načela Voronojevih diagramov za ustvarjanje silikonskih kalupov, izdelanih s [[3D-tiskalnik|3D-tiskalnikom]], za oblikovanje svojih izvirnih [[torta|tort]].

== Algoritmi ==

[[slika:Voronoi diagram with two points.svg|thumb|right|[[polravnina|Polravnini]] <math display="inline"> H_{pq} \!\, </math> in <math display="inline"> H_{qp} \!\, </math> sta ločeni s [[simetrala daljice|simetralo daljice]].]]
[[slika:Fortunes-algorithm-slowed.gif|thumb|right|Animacija [[Fortuneov algoritem|Fortuneovega algoritma]]]]

V preprostem [[algoritem|algoritmu]] [[simetrala daljice]] povezuje nek poljubni par točk <math display="inline"> p \!\, </math> in <math display="inline"> q \!\, </math>. Takšna simetrala razdeli ravnino na dve [[polravnina|polravnini]] <math display="inline"> H_{pq} \!\, </math> in <math display="inline"> H_{qp} \!\, </math>, pri čemer je Voronojevo območje <math display="inline"> p \!\, </math> v celoti v eni od njiju, območje točke <math display="inline"> q \!\, </math> pa v drugi. Voronojevo območje <math display="inline"> V_{p} \!\, </math> točke <math display="inline"> p \!\, </math> sovpada s presečiščem vseh takih polravnin <math display="inline"> H_{pq} \!\, </math>:

: <math> V_{p} = \bigcap \limits_{q \in S / \{p\}} H_{pq} \!\, . </math>

Tako se rešitev problema zmanjša na izračun takega presečišča za vsako točko <math display="inline"> p \!\, </math>. Algoritem je mogoče implementirati z [[časovna zahtevnost|zahtevnostjo]] <math display="inline"> O(n^{4}) \!\, </math>.{{r|spl3}}

Znanih je več učinkovitih algoritmov za konstrukcijo Voronojevih diagramov, tako neposrednih (kot za diagram sam) ali posrednih s konstrukcijo [[Delaunayeva triangulacija|Delaunayeve triangulacije]] in nato pridobitvijo njenega [[dualni graf|duala]]. Med neposredne algoritme spada [[Fortuneov algoritem|Fortuneov algoritem]], algoritem za generiranje Voronojevih diagramov iz množice točk v ravnini z zahtevnostjo <math display="inline"> O(n \log n) \!\, </math>.

[[Boyer-Watsonov algoritem]], algoritem za generiranje Delaunayeve triangulacije v poljubni razsežnosti z zahtevnostjo od <math display="inline"> O(n \log n) \!\, </math> do <math display="inline"> O(n^{2}) \!\, </math>, se lahko uporabi kot posredni algoritem za Voronojev diagram.

[[Algoritem poplavljanja skokov]] lahko generira [[približni Voronojev diagram|približne Voronojeve diagrame]] v konstantnem času in je primeren za uporabo na osnovni grafični strojni opremi.{{r|rong_2006}}{{r|spl4}}

[[Lloydov algoritem]] in njegova posplošitev z [[Linde-Buzo-Grayev algoritem|Linde-Buzo-Grayevim algoritmom]] (alias [[razvrščanje z voditelji]]) uporabljata konstrukcijo Voronojevih diagramov kot [[podprogram]]. Te metode se izmenjujejo med koraki, v katerih se sestavi Voronojev diagram za množico začetnih točk, in koraki, v katerih se začetne točke premaknejo v nove lege, ki so bolj usrediščene znotraj svojih celic. Te metode je mogoče uporabiti v prostorih poljubnih razsežnosti za iterativno konvergiranje k posebni obliki Voronojevega diagrama, imenovani [[centroidna Voronojeva teselacija]], kjer so bila mesta premaknjena na točke, ki so tudi geometrijska središča njihovih celic.

Glavna zamisel rekurzivnega algoritma je uporaba metode [[dinamično programiranje|dinamičnega programiranja]]. Začetna množica točk <math display="inline"> S \!\, </math> je razdeljena na dve [[podmožica|podmnožici]] <math display="inline"> S_{1} \!\, </math> in <math display="inline"> S_{2} \!\, </math>, za vsako od njih pa je izdelan Voronojev diagram, nato pa se dobljena diagrama združita v enega. Razdelitev množice <math display="inline"> S \!\, </math> se izvede s pomočjo premice, ki deli ravnino na dve polravnini, tako da obe polravnini vsebujeta približno enako število točk. Združevanje Voronojevih diagramov množic <math display="inline"> S_{1} \!\, </math> in <math display="inline"> S_{2} \!\, </math> je mogoče izvesti v času <math display="inline"> O(n) \!\, </math>, tako da je zahtevnost takšnega algoritma enaka <math display="inline"> O(n \log n) \!\, </math>.

== Glej tudi ==

{{div col}}
* [[Delaunayeva triangulacija]]
* [[delitev zemljevida]]
* [[problem o pravičnem rezanju torte]]
* [[izrek o sendviču s šunko]]
* [[metoda naravnih elementov]]
* [[interpolacija naravnih sosedov]] ([[Voronojeva interpolacija]], [[Sibsonova interpolacija]])
* [[interpolacija najbližjega soseda]]
* [[iskanje najbližjega soseda]]
* [[močnostni diagram]] ([[Laguerrov diagram]])
* [[Voronojev pol]]
{{div col end}}

== Sklici ==

{{refbegin|4|normalfont=yes}}
{{sklici|refs=
<ref name="arya_2002">{{sktxt|Arya|Malamatos|Mount|2002}}.</ref>
<ref name="aure_1991">{{sktxt|Aurenhammer|1991}}.</ref>
<ref name="baye_2020">{{sktxt|Bayer|Kunkel|Mara|2020}}. {{YouTube|VPqsY4tzwWA|GigaMesh Tutorial 10 - Voronoi Cells & Geodesic Distances - Sabouroff head}}. Analiza uporabe programja [[GigaMesh Software Framework]], kot je opisana v {{sktxt|Hölscher|Krömker|Mara|2020}}.</ref>
<ref name="berg_2008">{{sktxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2008}}.</ref>
<ref name="bied_2016">{{sktxt|Biedl|Grimm|Palios|Shewchuk|2016}}.</ref>
<ref name="bock_2009">{{sktxt|Bock|Tyagi|Kreft|Alt|2009}}.</ref>
<ref name="boyd_2004">{{sktxt|Boyd|Vandenberghe|2004}}.</ref>
<ref name="burr_2015">{{sktxt|Burrough|McDonnell|McDonnell|Lloyd|2015}}.</ref>
<ref name="cort_2004">{{sktxt|Cortés|Martinez|Karataş|Bullo|2004}}.</ref>
<ref name="diri_1850">{{sktxt|Dirichlet|1850}}.</ref>
<ref name="edel_2012">{{sktxt|Edelsbrunner|2012}}.</ref>
<ref name="fanf_2007">{{sktxt|Fanfoni|Placidi|Arciprete|Orsini|2007}}.</ref>
<ref name="fein_2021">{{sktxt|Feinstein|Shi|Ramanujam|Brylinski|2021}}.</ref>
<ref name="hoel_2020">{{sktxt|Hölscher|Krömker|Mara|2020}}.</ref>
<ref name="hui__2012">{{sktxt|Hui|Kang|Taehyong|Aidong|2012}}.</ref>
<ref name="john_2006">{{sktxt|Johnson|2006}}.</ref>
<ref name="kasi_2017">{{sktxt|Kasim|2017}}.</ref>
<ref name="loeb_2019">{{sktxt|Löbl|Zhai|Jahn|Ritzmann|2019}}.</ref>
<ref name="long_2005">{{sktxt|Longley|Goodchild|Maguire|Rhind|2005}}.</ref>
<ref name="lope_2019">{{sktxt|Lopez|Zhao|Magniol|Chiabaut|2019}}.</ref>
<ref name="mitc_1997">{{sktxt|Mitchell|1997}}.</ref>
<ref name="miya_2009">{{sktxt|Miyamoto|Moutanabbir|Haller|Itoh|2009}}.</ref>
<ref name="mulh_1996">{{sktxt|Mulheran|Blackman|1996}}.</ref>
<ref name="niu__2019">{{sktxt|Niu|Savvaris|Tsourdos|Ji|2019}}.</ref>
<ref name="okab_2000">{{sktxt|Okabe|Boots|Sugihara|Chiu|2000}}.</ref>
<ref name="pimp_2014">{{sktxt|Pimpinelli|Tumbek|Winkler|2014}}.</ref>
<ref name="reem_2009">{{sktxt|Reem|2009}}.</ref>
<ref name="reem_2011">{{sktxt|Reem|2011}}.</ref>
<ref name="rong_2006">{{sktxt|Rong|Tan|2006}}.</ref>
<ref name="sanc_2016">{{sktxt|Sanchez-Gutierrez|Tozluoglu|Barry|Pascual|2016}}.</ref>
<ref name="sen__2016">{{sktxt|Sen|2016}}.</ref>
<ref name="shen_2021">{{sktxt|Shenwai|2021}}.</ref>
<ref name="sing_2019">{{sktxt|Singh|Sadeghi|Correns|Blass|2019}}.</ref>
<ref name="skyu_1991">{{sktxt|Skyum|1991}}.</ref>
<ref name="spri_2010">{{sktxt|Springel|2010}}.</ref>
<ref name="teru_2021">{{sktxt|Teruel|Aragues|López-Nicolás|2021}}.</ref>
<ref name="thie_1911">{{sktxt|Thiessen|1911}}.</ref>
<ref name="tran_2009">{{sktxt|Tran|Tainar|Safar|2009}}.</ref>
<ref name="voro_1908">{{sktxt|Voronoï|1908a}} in {{sktxt|Voronoï|1908b}}.</ref>
<ref name="spl0">{{navedi splet|title= GOLD COAST CULTURAL PRECINCT|url= http://www.a-r-m.com.au/projects_GoldCoastCP.html|publisher= ARM Architecture|language= en|accessdate= 15. oktobra 2022|archive-date= 7. julija 2016|archive-url= https://web.archive.org/web/20160707155535/http://www.a-r-m.com.au/projects_GoldCoastCP.html|url-status= dead}}</ref>
<ref name="spl1">Arhivirano na [https://ghostarchive.org/varchive/youtube/20211211/90NsjKvz9Ns Ghostarchive]{{cbignore}} in [https://web.archive.org/web/20140611194118/http://www.youtube.com/watch?v=90NsjKvz9Ns&gl=US&hl=en Wayback Machine]{{cbignore}}: {{navedi splet|url= https://www.youtube.com/watch?v=90NsjKvz9Ns|title= Mark DiMarco: User Interface Algorithms [JSConf2014]|via= www.youtube.com}}{{cbignore}}</ref>
<ref name="spl2">{{navedi splet|url= https://www.education.vic.gov.au/parents/going-to-school/Pages/zones-restrictions.aspx|title= School zones|website= Victorian Government Department of Education and Training|language= en|access-date= 24. avgusta 2020|archive-date= 2020-08-11|archive-url= https://web.archive.org/web/20200811131939/https://education.vic.gov.au/parents/going-to-school/Pages/zones-restrictions.aspx|url-status= dead}}</ref>
<ref name="spl3">{{navedi splet|url=http://e-maxx.ru/algo/voronoi_diagram_2d_n4|title= Диаграмма Вороного в 2D|website= MAXimal|date= 26. januar 2009|access-date= 8. junija 2021|language= ru|archivedate= 8. junija 2021|archiveurl= https://web.archive.org/web/20210608205907/http://e-maxx.ru/algo/voronoi_diagram_2d_n4|url-status= live}}</ref>
<ref name="spl4">{{navedi splet|url= https://www.shadertoy.com/view/4syGWK|title= Jump Flooding|date= 24. februar 2016|website= Shadertoy|language= en}}</ref>
}}
{{refend}}

== Viri ==

{{refbegin|1|normalfont=yes}}
* {{citat|last1= Arya|first1= Sunil|last2= Malamatos|first2= Theocharis|last3= Mount|first3= David Mark|authorlink3= David Mark Mount|title= Proceedings of the thiry-fourth annual ACM symposium on Theory of computing|date= 2002|chapter= Space-efficient approximate Voronoi diagrams|pages= 721–730|isbn= 1581134959|doi= 10.1145/509907.510011|s2cid=1727373}}
* {{citat|last1= Aurenhammer|first1= Franz|authorlink1= Franz Aurenhammer|title= Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure|journal= ACM Computing Surveys|date= 1991|volume= 23|issue= 3|pages= 345–405|doi= 10.1145/116873.116880|s2cid= 4613674}}
* {{citat|last1= Bayer|first1= Paul Victor|last2= Kunkel|first2= Selina|last3= Mara|first3= Hubert|title= GigaMesh Software Framework Tutorial 10: Geodesic Distance & Voronoi Cells (Sabouroff head)|date= marec 2020|doi= 10.11588/heidok.00027985}}
* {{citat|last1= Biedl|first1= Therese|authorlink1= Therese Biedl|last2= Grimm|first2= Carsten|last3= Palios|first3= Leonidas|last4= Shewchuk|first4= Jonathan|authorlink4= Jonathan Shewchuk|last5= Verdonschot|first5= Sander|contribution= Realizing farthest-point Voronoi diagrams|title= Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016)|date= 2016}}
* {{citat|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]]|date= 2009|volume= 72|issue= 7|pages= 1696–1731|issn= 0007-4985|doi= 10.1007/s11538-009-9498-3|pmid= 20082148|arxiv= 0901.4469v1|bibcode= 2009arXiv0901.4469B|s2cid= 16074264}}
* {{citat|last1= Bowyer|first1= Adrian|authorlink1= Adrian Bowyer|title= Computing Dirichlet tessellations|journal= [[The Computer Journal]]|date= 1981|volume= 24|issue= 2|pages= 162–166|issn= 0010-4620|doi= 10.1093/comjnl/24.2.162|doi-access= free}}
* {{citat|last1= Boyd|first1= Stephen P.|last2= Vandenberghe|first2= Lieven|title= Convex Optimization|date= 2004|publisher= [[Cambridge University Press]]|chapter= Exercise 2.9|page= 60|isbn= 0-521-83378-7|cobiss= 512546423|url= https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf}}
* {{citat|last1= Burrough|first1= Peter A.|last2= McDonnell|first2= Rachael|last3= McDonnell|first3= Rachael A.|last4= Lloyd|first4= Christopher D.|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|date= 2015|publisher= [[Oxford University Press]]|isbn= 978-0-19-874284-5|pages= 160–}}
* {{citat|last1= Cortés|first1= Jorge|last2= Martinez|first2= Sonia|last3= Karataş|first3= Timur|last4= Bullo|first4= Francesco|title= Coverage control for mobile sensing networks|journal= [[IEEE Transactions on Robotics and Automation]]|date= 13. april 2004|volume= 20|issue= 2|pages= 243–255|doi= 10.1109/TRA.2004.824698|s2cid= 2022860|issn= 2374-958X}}
* {{citat|last1= de Berg|first1= Mark|authorlink1= Mark de Berg|last2= van Kreveld|first2= Marc|authorlink2= Marc van Kreveld|last3= Overmars|first3= Mark|authorlink3= Mark Overmars|last4= Schwarzkopf|first4= Otfried|authorlink4= Otfried Schwarzkopf|title= Computational Geometry|date= 2008|publisher= [[Springer-Verlag]]|edition= 3.|isbn= 978-3-540-77974-2|chapter= 7.4 Farthest-Point Voronoi Diagrams}} – vsebuje opis algoritma.
* {{citat|last1= Dirichlet|first1= Gustav Lejeune|authorlink1= Johann Peter Gustav Lejeune Dirichlet|title= Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen|journal= [[Journal für die Reine und Angewandte Mathematik]]|date= 1850|volume= 1850|issue= 40|pages= 209–227|doi= 10.1515/crll.1850.40.209|s2cid= 199546675}}
* {{citat|last1= Edelsbrunner|first1= Herbert|authorlink1= Herbert Edelsbrunner|title= Algorithms in Combinatorial Geometry|date= 2012|chapter= 13.6 Power Diagrams|pages= 327–328|publisher= Springer-Verlag|series= (EATCS Monographs on Theoretical Computer Science)|volume= 10|orig-year= 1987|isbn= 9783642615689}}
* {{citat|last1= Fanfoni|first1= Massimo|last2= Placidi|first2= Ernesto|last3= Arciprete|first3= Fabrizio|last4= Orsini|first4= Elena|last5= Patella|first5= Fulvia|last6= Balzarotti|first6= Adalberto|title= Sudden nucleation versus scale invariance of InAs quantum dots on GaAs|journal= Physical Review B|date= 2007|volume= 75|issue= 24|pages= 245312|issn= 1098-0121|doi= 10.1103/PhysRevB.75.245312|bibcode= 2007PhRvB..75x5312F|s2cid= 120017577}}
* {{citat|last1= Feinstein|first1= Joseph|last2= Shi|first2= Wentao|last3= Ramanujam|first3= J.|last4= Brylinski|first4= Michal|title= Bionoi: A Voronoi Diagram-Based Representation of Ligand-Binding Sites in Proteins for Machine Learning Applications|date= 2021|work= Protein-Ligand Interactions and Drug Design|pages= 299–312|editor-last1= Ballante|editor-first1= 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|volume= 2266|pmid= 33759134|s2cid= 232338911}}
* {{citat|last1= Hölscher|first1= Tonio|last2= Krömker|first2= Susanne|last3= Mara|first3= Hubert|authorlink3= Hubert Mara|title= Gedenkschrift für Georgios Despinis|date= 2020|chapter= Der [[glava Saburova|Kopf Sabouroff]] in Berlin: Zwischen archäologischer Beobachtung und geometrischer Vermessung|publisher= [[Muzej Benaki]]|location= Atene, Grčija|language= de}}
* {{citat|last1= Hui|first1= Li|last2= Kang|first2= Li|last3= Taehyong|first3= Kim|last4= Aidong|first4= Zhang|last5= Murali|first5= Ramanathan|editor1-last= Baskurt|editor1-first= Atilla M.|editor2-last= Sitnik|editor2-first= Robert|title= Spatial Modeling of Bone Microarchitecture|journal= Three-Dimensional Image Processing (3Dip) and Applications Ii|date= marec 2012|volume= 8290|pages= 82900P|bibcode= 2012SPIE.8290E..0PL|doi= 10.1117/12.907371|s2cid= 1505014}}
* {{citat|last1= Johnson|first1= Steven|title= The Ghost Map: The Story of London's Most Terrifying Epidemic — and How It Changed Science, Cities, and the Modern World|date= 19. oktober 2006|url= https://books.google.com/books?id=8R3NrzE8veEC&pg=PT187|access-date= 16. oktobra 2017|publisher= Penguin Publishing Group|isbn= 978-1-101-15853-1|page= 187}}
* {{citat|last1= Kasim|first1= Muhammad Firmansyah|title= Quantitative shadowgraphy and proton radiography for large intensity modulations|journal= [[Physical Review E]]|date= 1. januar 2017|volume= 95|issue= 2|pages= 023306|doi= 10.1103/PhysRevE.95.023306|pmid= 28297858|arxiv= 1607.04179|bibcode= 2017PhRvE..95b3306K|s2cid= 13326345}}
* {{citat|last1= Klein|first1= Rolf|title= Computational Geometry and its Applications|chapter= Abstract Voronoi diagrams and their applications|series= ([[Lecture Notes in Computer Science]])|date= 1989|volume= 333|pages= 148–157|publisher= Springer|doi= 10.1007/3-540-50335-8_31|isbn= 978-3-540-52055-9}}
* {{citat|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|date= 3. oktober 2019|volume= 100|issue= 15|page= 155402|issn= 2469-9950|doi= 10.1103/physrevb.100.155402|arxiv= 1902.10145|bibcode= 2019PhRvB.100o5402L|s2cid= 119443529}}
* {{citat|last1= Longley|first1= Paul A.|last2= Goodchild|first2= Michael F.|last3= Maguire|first3= David J.|last4= Rhind|first4= David W.|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 (založba)|Wiley]]|isbn= 978-0-470-87001-3|pages= 333–}}
* {{citat|last1= Lopez|first1= Clélia|last2= Zhao|first2= Chuan-Lin|last3= Magniol|first3= Stéphane|last4= Chiabaut|first4= Nicolas|last5= Leclercq|first5= Ludovic|title= Microscopic Simulation of Cruising for Parking of Trucks as a Measure to Manage Freight Loading Zone|journal= [[Sustainability (revija)|Sustainability]]|date= 28. februar 2019|volume= 11|issue= 5|pages= 1276|issn= 2071-1050|doi= 10.3390/su11051276}}
* {{citat|last1= Mitchell|first1= Tom Michael|title= Machine Learning|date= 1997|publisher= McGraw-Hill|edition= mednarodna|isbn= 978-0-07-042807-2|cobiss= 	3792935|page=[https://archive.org/details/machinelearning00mitc_087/page/n244 233]|url= https://archive.org/details/machinelearning00mitc_087 |url-access= limited}}
* {{citat|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|date= 2009|volume= 79|issue= 165415 |pages= 165415|issn= 1098-0121|doi= 10.1103/PhysRevB.79.165415|bibcode= 2009PhRvB..79p5415M|s2cid= 13719907|url= https://semanticscholar.org/paper/a69dd35b6bc204d9d1abb16aead589d1832f1528}}
* {{citat|last1= Mulheran|first1= Paul A.|last2= Blackman|first2= John A.|title= Capture zones and scaling in homogeneous thin-film growth|journal= [[Physical Review B|Physical Review B (Condensed Matter)]]|date= 15. april 1996|volume= 53|issue= 15|pages= 10261–10267|doi= 10.1103/PhysRevB.53.10261|pmid= 9982595|bibcode= 1996PhRvB..5310261M}}
* {{citat|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= [[Journal of Navigation]]|date= 24. januar 2019|volume= 72|issue= 4|pages= 850–874|issn= 0373-4633|doi= 10.1017/S0373463318001005|s2cid= 67908628|url= https://orca.cardiff.ac.uk/118170/1/Voronoi-Visibility%20Roadmap-based%20Path%20Planning%20Algorithm%20for%20Unmanned%20Su.._.pdf}}
* {{citat|last1= Okabe|first1= Atsuyuki|last2= Boots|first2= Barry|last3= Sugihara|first3= Kokichi|last4= Chiu|first4= Sung Nok|title= Spatial Tessellations – Concepts and Applications of Voronoi Diagrams|date= 2000|edition= 2.|publisher= John Wiley|isbn= 978-0-471-98635-5|cobiss= 9520729}}
* {{citat|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]]|date= 2014|volume= 5|issue= 6|pages= 995–998|doi= 10.1021/jz500282t|pmid= 24660052|pmc= 3962253}}
* {{citat|last1= Reem|first1= Daniel|title= An algorithm for computing Voronoi diagrams of general generators in general normed spaces| journal= Proceedings of the Sixth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2009)|date= 2009|pages= 144–152|doi= 10.1109/ISVD.2009.23|isbn= 978-1-4244-4769-5}}
* {{citat|last1= Reem|first1= Daniel|title= The geometric stability of Voronoi diagrams with respect to small changes of the sites|journal= Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG)|date= 2011|pages= 254–263|arxiv= 1103.4125|doi= 10.1145/1998196.1998234|isbn= 9781450306829|bibcode= 2011arXiv1103.4125R|s2cid= 14639512}}
* {{citat|last1= Rong|first1= Guodong|last2= Tan|first2= Tiow Seng|editor1-last= Olano|editor1-first= Marc|editor2-last= Séquin|editor2-first= Carlo H.|contribution= Jump flooding in GPU with applications to Voronoi diagram and distance transform|contribution-url= https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf|doi= 10.1145/1111411.1111431|pages= 109–116|publisher= ACM|title= Proceedings of the 2006 Symposium on Interactive 3D Graphics, SI3D 2006, March 14-17, 2006, Redwood City, California, USA|date= 2006}}
* {{citat|last1= Sanchez-Gutierrez|first1= Daniel|last2= Tozluoglu|first2= Melda|last3= Barry|first3= Joseph D.|last4= Pascual|first4= Albero|last5= Mao|first5= Yanlan|last6= Escudero|first6= Luis M.|title= Fundamental physical cellular constraints drive self-organization of tissues|journal= [[The EMBO Journal]]|date= 4. januar 2016|volume= 35|issue= 1|pages= 77–88|issn= 0261-4189|doi= 10.15252/embj.201592374|pmc= 4718000|pmid= 26598531}}
* {{citat|last1= Sen|first1= Zekai|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|edition= 2.|publisher= [[Springer Science+Business Media|Springer]]|isbn= 978-3-319-41758-5|pages= 57–}}
* {{citat|last1= Shenwai|first1= Tanushree|title= A Novel Deep Learning Technique That Rebuilds Global Fields Without Using Organized Sensor Data|date= 18. november 2021|url= https://www.marktechpost.com/2021/11/18/a-novel-deep-learning-technique-that-rebuilds-global-fields-without-using-organized-sensor-data/|access-date= 5. decembra 2021|website= MarkTechPost|language= en-US}}
* {{citat|last1= Singh|first1= Kushagra|last2= Sadeghi|first2= Farshid|last3= Correns|first3= Martin|last4= Blass|first4= Toni|title= A microstructure based approach to model effects of surface roughness on tensile fatigue|journal= International Journal of Fatigue|date= december 2019|volume= 129|page= 105229|issn= 0142-1123|doi= 10.1016/j.ijfatigue.2019.105229|s2cid= 202213370}}
* {{citat|last1= Skyum|first1= Sven|title= A simple algorithm for computing the smallest enclosing circle|journal= Information Processing Letters|date= 18. februar 1991|volume= 37|issue= 3|pages= 121–125|doi= 10.1016/0020-0190(91)90030-L}} – vsebuje preprost algoritem za računanje Voronojevega diagrama najoddaljenejše točke.
* {{citat|last1= Springel|first1= Volker|title= E pur si muove: Galilean-invariant cosmological hydrodynamical simulations on a moving mesh|journal= [[Monthly Notices of the Royal Astronomical Society|MNRAS]]|date= 2010|volume= 401|issue= 2|pages= 791–851|doi= 10.1111/j.1365-2966.2009.15715.x|bibcode= 2010MNRAS.401..791S|arxiv= 0901.4107|s2cid= 119241866}}
* {{citat|last1= Teruel|first1= Enrique|last2= Aragues|first2= Rosario|last3= López-Nicolás|first3= Gonzalo|title= A Practical Method to Cover Evenly a Dynamic Region With a Swarm|journal= IEEE Robotics and Automation Letters|date= april 2021|volume= 6|issue= 2|pages= 1359–1366|doi= 10.1109/LRA.2021.3057568|s2cid= 232071627|issn= 2377-3766}}
* {{citat|last1= Thiessen|first1= Alfred Henry|authorlink1= Alfred Henry Thiessen|title= Precipitation averages for large areas|journal= [[Monthly Weather Review]]|date= 1. julij 1911|volume= 39|issue= 7|pages= 1082–1084|issn= 0027-0644|doi= 10.1175/1520-0493(1911)39<1082b:PAFLA>2.0.CO;2}}
* {{citat|last1= Tran|first1= Quoc Thai|last2= Tainar|first2= David|last3= Safar|first3= Maytham|chapter= Reverse k Nearest Neighbor and Reverse Farthest Neighbor Search on Spatial Networks|title= Transactions on Large-Scale Data- and Knowledge-Centered Systems I|date= 2009|page= 357|editor-last1= Hameurlain|editor-first1= Abdelkader|editor-last2= Küng|editor-first2= Josef|editor-last3= Wagner|editor-first3= Roland|series= (Lecture notes in computer science)|volume= 5740|isbn= 978-3-642-03721-4|cobiss= 35429981}}
* {{citat|last1= Voronoï|first1= Georges|authorlink1= Georgij Feodosjevič Voronoj|title= Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier mémoire. Sur quelques propriétés des formes quadratiques positives parfaites.|journal= Journal für die Reine und Angewandte Mathematik|date= 1908a|volume= 1908|issue= 133|pages= 97–178|doi= 10.1515/crll.1908.133.97|s2cid= 116775758|url= https://gdz.sub.uni-goettingen.de/download/pdf/PPN243919689_0133/LOG_0010.pdf}}
* {{citat|last1= Voronoï|first1= Georges|title= Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs.|journal= Journal für die Reine und Angewandte Mathematik|date= 1908b|volume= 1908|issue= 134|pages= 198–287|doi= 10.1515/crll.1908.134.198|s2cid= 118441072|url= https://gdz.sub.uni-goettingen.de/download/pdf/PPN243919689_0134/LOG_0014.pdf}}
* {{citat|last1= Watson|first1= David F.|title= Computing the ''n''-dimensional Delaunay tessellation with application to Voronoi polytopes|journal= The Computer Journal|date= 1981|volume= 24|issue= 2|pages= 167–172|doi= 10.1093/comjnl/24.2.167|doi-access= free}}
{{refend}}

== Zunanje povezave ==

{{kategorija v Zbirki|Voronoi diagrams|Voronojev diagram}}
* {{MathWorld|id=VoronoiDiagram|title=Voronoi Diagram}}
* [http://www.cgal.org/Part/VoronoiDiagrams Voronoi Diagrams] v programski knjižnici algoritmov računalniške keometrije [[CGAL]] (''Computational Geometry Algorithms Library'') {{in lang|en}}

{{normativna kontrola}}

[[Kategorija:Diskretna geometrija]]
[[Kategorija:Računalniška geometrija]]
[[Kategorija:Diagrami]]
[[Kategorija:Ukrajinski izumi]]
[[Kategorija:Ruski izumi]]
[[Kategorija:Geografski informacijski sistemi]]
[[Kategorija:1908 v znanosti]]