Voronojev diagram

20 naključnih točk v ravnini in njihove Voronojeve celice (večja različica spodaj)

Thiessnovi mnogokotniki

Fotografija nevronov (levo) in ustrezni Voronojev mozaik, zgrajen na podlagi njihovih centroidov (geometrijskih središč)

Voronojev diagrám [voronójev ~] je v matematiki razdeljevanje 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č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 dveh razsežnostih je dualen svoji ustrezni Delaunayevi triangulaciji v smislu teorije grafov.

Voronojev diagram se imenuje po ruskem matematiku Georgiju Feodosjeviču Voronoju, ki jih je leta 1908 definiral in raziskoval splošni n-razsežni primer. Imenuje se tudi Voronojeva teselacija (~ pokritje, ~ tlakovanje), Voronojeva dekompozicija, Voronojeva particija ali Dirichletova teselacija (po Johannu Petru Gustavu Lejeunu Dirichletu). Voronojeve celice so znane tudi kot Thiessnovi mnogokotniki, še posebej v znanostih o Zemlji (geofiziki, meteorologiji in klimatologiji). Imenujejo se po ameriškem meteorologu Alfredu Henryju Thiessnu. Voronojevi diagrami se praktično in teoretično uporabljajo na številnih področjih, predvsem v znanosti in tehnologiji, pa tudi v likovni umetnosti.

Najpreprostejši primer

V najpreprostejšem primeru, prikazanem na prvi sliki, je končna množica točk $\{p_{1},\ldots ,p_{n}\}\!\,$ v evklidski ravnini. V tem primeru je vsako mesto $p_{k}\!\,$ preprosto točka in njena ustrezna Voronojeva celica $R_{k}\!\,$ je sestavljena iz vsake točke v evklidski ravnini, katere razdalja do točke $p_{k}\!\,$ je manjša ali enaka njeni razdalji do katere koli druge točke $p_{k}\!\,$. Vsaka taka celica je pridobljena iz presečišča polprostorov in je torej (konveksni) polieder. Daljice, (v tem primeru stranice nastalih mnogokotnikov), Voronojevega diagrama so vse točke v ravnini, ki so enako oddaljene od dveh najbližjih mest. Voronojeva oglišča (vozlišča) so točke, ki so enako oddaljene od treh (ali več) mest.

Formalna definicija

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

$R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{za vse}}\;j\neq k\}\!\,.$

Voronojev diagram je preprosto trojica celic ${\textstyle (R_{k})_{k\in K}\!\,}$. 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 geometriji števil in kristalografiji), vendar je v mnogih primerih upoštevanih le končno veliko mest.

V posebnem primeru, ko je 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 politopi 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 ${\textstyle R_{k}\!\,}$ je povezan z generatorsko točko ${\textstyle P_{k}\!\,}$. Naj je ${\textstyle X}$ množica vseh točk v evklidskem prostoru. ${\textstyle P_{1}}$ naj je točka, ki generira Voronojevo območje ${\textstyle R_{1}\!\,}$, ${\textstyle P_{2}\!\,}$, ki genrira ${\textstyle R_{2}\!\,}$ in ${\textstyle P_{3}\!\,}$, ki generira ${\textstyle R_{3}\!\,}$ in tako naprej. Potem, kot je navedeno v Tran; Tainar; Safar (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 ${\textstyle R_{k}\!\,}$ dane trgovine ${\textstyle P_{k}\!\,}$ 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 evklidsko razdaljo:

$\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}}}\!\,$

ali z manhattansko razdaljo:

$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|\!\,.$

Odgovarjajoča Voronojeva diagrama izgledata različno za različno metriko razdalje.

Voronojeva diagrama na 20-ih točkah za dve različni metriki

evklidska razdalja

manhattanska razdalja

Značilnosti

• dualni graf za Voronojev diagram (v primeru evklidskega prostora s točkovnimi mesti) odgovarja Delaunayevi triangulaciji za isto množico 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 konveksni ogrinjači, če in samo če si njune Voronojeve celice delijo neskončno dolgo stranico.
• če je 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. 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 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. Kot je prikazano tam, ta značilnost na splošno ne velja, tudi če je prostor dvorazsežen (vendar neuniformno konveksen in zlasti neevklidski) in so mesta točke.

Zgodovina in raziskovanje

Neformalno rabo Voronojevih diagramov se lahko najde pri Renéju Descartesu leta 1644. Johann Peter Gustav Lejeune Dirichlet je uporabil dvorazsežne in trirazsežne Voronojeve diagrame pri svojem raziskovanju 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 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 Georgiju Feodosjeviču Voronoju, ki je definiral in raziskoval splošni n-razsežni primer leta 1908. Voronojevi diagrami, ki se uporabljajo v geofiziki in meteorologiji za analizo prostorsko porazdeljenih podatkov (na primer merjenje padavin), se imenujejo po ameriškem meteorologu Alfredu Henryju Thiessnu. V kristalografiji in fiziki kondenzirane snovi so takšna pokritja znana tudi kot 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

To je rezina Voronojevega diagrama za naključno množico točk v trirazsežni kocki. V splošnem presek trirazsežnega Voronojevega pokritja ni dvorazsežno Voronojevo pokritje sámo. (Celice so vse konveksni poliedri.)

Voronojevo pokritje pravilnih mrež točk v dveh ali treh razsežnostih da mnogo znanih pokritij.

• dvorazsežna mreža točk da nepravilno pokritje satovja z enakimi šestkotniki s točkovno simetrijo. V primeru pravilne trikotniške mreže točk je pokritje pravilno – Voronojeve celice so pravilni šestkotniki. V primeru pravokotniške mreže točk se šestkotniki skrčijo v pravokotnike v vrsticah in stolpcih. 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 trikotniško pokritje.
• enostavna kubična mreža da kubično satovje.
• šestkotniška tesno pakirana mreža da pokritje prostora s trapezorombskimi dodekaedri.
• ploskovno centrirana kubična mreža da pokritje prostora z rombskimi dodekaedri.
• telesno centrirana kubična mreža da pokritje prostora s 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-šestskotniškimi dodekaedri.

Za množico točk ${\textstyle (x,y)\!\,}$ z ${\textstyle x\!\,}$ v diskretni množici ${\textstyle X\!\,}$ in ${\textstyle y\!\,}$ v diskretni množici ${\textstyle Y\!\,}$ 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 ${\textstyle S\!\,}$, je Voronojeva celica n-tega reda definirana kot množica točk, ki ima določeno množico n točk v ${\textstyle S\!\,}$ 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 ${\textstyle S\!\,}$ se začne z diagramom reda ${\textstyle n-1\!\,}$ in vsaka celica, generirana z ${\textstyle X=\{x_{1},x_{2},\ldots ,x_{n-1}\}\!\,}$, se zamenja z Voronojevim diagramom, generiranim na množici ${\textstyle S-X\!\,}$.

Voronojev diagram najoddaljenejše točke

Za dano množico n točk se Voronojev diagram reda ${\textstyle n-1\!\,}$ imenuje Voronojev diagram najoddaljenejše točke.

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

Meje celic v Voronojevem diagramu najoddaljenejše točke imajo strukturo topološkega drevesa z neskončnimi poltrakovi kot listi. Vsako končno drevo je izomorfno drevesu, oblikovanemu na ta način iz Voronojevega diagrama najoddaljenejše točke.

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.

Približni Voronojev diagram za množico točk. Vidne so mešane barve na mehki meji Voronojevih celic.

V 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 metrika, so lahko v tem primeru nekatere Voronojeve celice prazne. Močnostni diagram je vrsta Voronojevega diagrama, definiranega iz množice krožnic z uporabo potenčne razdalje – lahko se ga predstavlja tudi kot uteženi Voronojev diagram, v katerem je utež, definirana iz polmera vsake krožnice, dodana kvadratu evklidske razdalje od središča krožnice.

Voronojev diagram n točk v d-razsežnem prostoru ima lahko ${\textstyle O(n^{\lceil d/2\rceil })}$ 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žnih Voronojevih diagramov.

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

Uporabe

Meteorologija in hidrologija

Uporablja se v meteorologiji in tehniški hidrologiji za iskanje uteži podatkov o padavinah postaj na območju (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 ${\textstyle (A_{i})\!\,}$, ki se dotika točke postaje, je znano kot vplivno območje postaje. Povprečno količino padavin se izračuna po formuli ${\textstyle {\bar {P}}={\frac {\sum A_{i}P_{i}}{\sum A_{i}}}\!\,}$

Glej tudi: Delaunayeva triangulacija § Uporabe

Humanistika

• v klasični arheologiji in še posebej v umetnostni zgodovini se simetrija glav kipov analizira za določitev kateri vrsti kipa bi lahko pripadala odrezana glava. Zgled tega, pri katerem so bile uporabljene Voronojeve celice, je bila identifikacija glave Saburova, ki je uporabila visokoločljivo mnogokotniško mrežo.
• v dialektometriji se Voronojeve celice rabijo za prikaz domnevne jezikovne kontinuitete med merilnimi točkami.

Naravoslovje

Voronojevo pokritje nastane z radialno rastjo iz semena navzven.

• v biologiji se Voronojevi diagrami rabijo za modeliranje mnogih različnih bioloških struktur, kot so na primer celice in mikroarhitektura kosti. Voronojeva pokritja dejansko delujejo kot geometrijsko orodje za razumevanje fizičnih omejitev, ki poganjajo organizacijo bioloških tkiv.
• v hidrologiji se Voronojevi diagrami rabijo za izračun količine padavin na območju na podlagi niza točkovnih meritev. V tej uporabi se na splošno imenujejo Thiessnovi mnogokotniki.
• v ekologiji se Voronojevi diagrami rabijo za preučevanje vzorcev rasti gozdov in gozdnih krošenj, lahko pa so tudi v pomoč pri razvoju napovednih modelov za gozdne požare.
• v računski kemiji se mesta za vezavo ligandov pretvorijo v Voronojeve diagrame za aplikacije strojnega učenja (na primer za razvrščanje veznih žepov v proteinih). V drugih aplikacijah se Voronojeve celice, definirane z legami jeder v molekuli, rabijo za izračun atomskih nabojev. To se naredi z metodo Voronojeve gostote deformacije.
• v 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 razmerja med signalom in šumom na vseh slikah.
• v računski dinamiki tekočin se lahko Voronojevo pokritje množice točk uporabi za določitev računskih domen za uporabo v metodah končnih prostornin, na primer kot v kodi kozmologije premikajoče se mreže AREPO.
• v računalniški fiziki se Voronojevi diagrami uporabljajo za izračun profilov telesa s senčnim grafom in protonsko radiografijo v fiziki visokih gostot energije.

Zdravje

• v medicinski diagnostiki se lahko uporabijo modeli mišičnih tkiv na podlagi Voronojevih diagramov za zaznavo nevromuskulaturnih bolezni.
• v epidemiologiji se Voronojevi diagrami lahko uporabljajo za korelacijo vzorcev okužb v epidemijah. Voronojeve diagrame je med prvimi izvedel angleški zdravnik John Snow za raziskovanje 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č smrtmi zaradi izbruha.

Inženirstvo

• v fiziki polimerov se lahko Voronojevi diagrami uporabljajo za prikaz prostih prostornin polimerov.
• v znanosti o materialih so polikristalinske mikrostrukture v kovinskih zlitinah običajno predstavljene s pomočjo Voronojevih pokritij. Pri rasti otokov se za oceno stopnje rasti posameznih otokov uporablja Voronojev diagram. V fiziki kondenzirane snovi je Wigner-Seitzeva celica Voronojevo pokritje trdnine, Brillouinova cona pa Voronojevo pokritje vzajemnega prostora kristalov, ki imajo simetrijo prostorske skupine (valovno število).
• v 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 arhutekturi so uporabili Voronojeve vzorce kot osnovo za zmagovalni vnos prenove kulturnega predela The Arts Center v Gold Coastu, Queensland, Avstralija.
• v urbanističnem načrtovanju se lahko Voronojevi diagrami uporabijo za ovrednotenje sistema Freight Loading Zone (območja nakladanja tovora).
• v 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 ploskovni metrologiji se lahko Voronojevo pokritje uporabi za modeliranje hrapavosti površin.
• v robotiki nekatere strategije nadzora in algoritmi za načrtovanje poti sistemov z več roboti temeljijo na Voronojevem razdeljevanju okolja.

Geometrija

• podatkovno strukturo lege točke se lahko zgradi prek Voronojevega diagrama za odgovor na poizvedbe 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 podatkovni zbirki. Velika uporaba je vektorska kvantizacija, ki se pogosto uporablja pri stiskanju podatkov.
• v geometriji se lahko Voronojevi diagrami uporabijo za iskanje 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. Voronojev pristop se uporablja tudi pri vrednotenju krožnosti/okroglosti pri ocenjevanju nabora podatkov iz koordinatnega merilnega stroja.

Informatika

• v računalniškem omrežju se lahko Voronojeve diagrame uporabi pri izpeljavah zmogljivosti brezžičnega omrežja.
• v računalniški grafiki se Voronojevi diagrami uporabljajo za izračun trirazsežnih geometrijskih vzorcev drobljenja in lomljenja. Uporabljajo se tudi za proceduralno ustvarjanje organskih ali lavastih tekstur.
• v neodvisni robotski navigaciji se Voronojevi diagrami uporabljajo za iskanje jasnih poti. Če so točke ovire, bodo povezave grafa poti, ki so najbolj oddaljene od ovir (in teoretično morebitnih trkov).
• pri strojnem učenju se Voronojevi diagrami uporabljajo za razvrščanje 1-NN.
• 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 globokim učenjem
• pri razvoju uporabniških vmesnikov je mogoče Voronojeve vzorce uporabiti za izračun najboljšega stanja lebdenja za dano točko.

Nauk o državi in načrtovanje

• V 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.

Pekarstvo

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

Algoritmi

Polravnini ${\textstyle H_{pq}\!\,}$ in ${\textstyle H_{qp}\!\,}$ sta ločeni s simetralo daljice.

Animacija Fortuneovega algoritma

V preprostem algoritmu simetrala daljice povezuje nek poljubni par točk ${\textstyle p\!\,}$ in ${\textstyle q\!\,}$. Takšna simetrala razdeli ravnino na dve polravnini ${\textstyle H_{pq}\!\,}$ in ${\textstyle H_{qp}\!\,}$, pri čemer je Voronojevo območje ${\textstyle p\!\,}$ v celoti v eni od njiju, območje točke ${\textstyle q\!\,}$ pa v drugi. Voronojevo območje ${\textstyle V_{p}\!\,}$ točke ${\textstyle p\!\,}$ sovpada s presečiščem vseh takih polravnin ${\textstyle H_{pq}\!\,}$:

$V_{p}=\bigcap \limits _{q\in S/\{p\}}H_{pq}\!\,.$

Tako se rešitev problema zmanjša na izračun takega presečišča za vsako točko ${\textstyle p\!\,}$. Algoritem je mogoče implementirati z zahtevnostjo ${\textstyle O(n^{4})\!\,}$.

Znanih je več učinkovitih algoritmov za konstrukcijo Voronojevih diagramov, tako neposrednih (kot za diagram sam) ali posrednih s konstrukcijo Delaunayeve triangulacije in nato pridobitvijo njenega duala. Med neposredne algoritme spada Fortuneov algoritem, algoritem za generiranje Voronojevih diagramov iz množice točk v ravnini z zahtevnostjo ${\textstyle O(n\log n)\!\,}$.

Boyer-Watsonov algoritem, algoritem za generiranje Delaunayeve triangulacije v poljubni razsežnosti z zahtevnostjo od ${\textstyle O(n\log n)\!\,}$ do ${\textstyle O(n^{2})\!\,}$, se lahko uporabi kot posredni algoritem za Voronojev diagram.

Algoritem poplavljanja skokov lahko generira približne Voronojeve diagrame v konstantnem času in je primeren za uporabo na osnovni grafični strojni opremi.

Lloydov algoritem in njegova posplošitev z 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čnega programiranja. Začetna množica točk ${\textstyle S\!\,}$ je razdeljena na dve podmnožici ${\textstyle S_{1}\!\,}$ in ${\textstyle S_{2}\!\,}$, za vsako od njih pa je izdelan Voronojev diagram, nato pa se dobljena diagrama združita v enega. Razdelitev množice ${\textstyle S\!\,}$ 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 ${\textstyle S_{1}\!\,}$ in ${\textstyle S_{2}\!\,}$ je mogoče izvesti v času ${\textstyle O(n)\!\,}$, tako da je zahtevnost takšnega algoritma enaka ${\textstyle O(n\log n)\!\,}$.

Glej tudi

• 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

Viri

• Arya, Sunil; Malamatos, Theocharis; Mount, David Mark (2002), »Space-efficient approximate Voronoi diagrams«, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, str. 721–730, doi:10.1145/509907.510011, ISBN 1581134959, S2CID 1727373
• 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
• Bayer, Paul Victor; Kunkel, Selina; Mara, Hubert (Marec 2020), GigaMesh Software Framework Tutorial 10: Geodesic Distance & Voronoi Cells (Sabouroff head), doi:10.11588/heidok.00027985
• Biedl, Therese; Grimm, Carsten; Palios, Leonidas; Shewchuk, Jonathan; Verdonschot, Sander (2016), »Realizing farthest-point Voronoi diagrams«, Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016)
• Bock, Martin; Tyagi, Amit Kumar; Kreft, Jan-Ulrich; Alt, Wolfgang (2009), »Generalized Voronoi Tessellation as a Model of Two-dimensional Cell Tissue Dynamics«, Bulletin of Mathematical Biology, 72 (7): 1696–1731, arXiv:0901.4469v1, Bibcode:2009arXiv0901.4469B, doi:10.1007/s11538-009-9498-3, ISSN 0007-4985, PMID 20082148, S2CID 16074264
• Bowyer, Adrian (1981), »Computing Dirichlet tessellations«, The Computer Journal, 24 (2): 162–166, doi:10.1093/comjnl/24.2.162, ISSN 0010-4620
• Boyd, Stephen P.; Vandenberghe, Lieven (2004), »Exercise 2.9«, Convex Optimization (PDF), Cambridge University Press, str. 60, COBISS 512546423, ISBN 0-521-83378-7
• 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, str. 160–, ISBN 978-0-19-874284-5
• Cortés, Jorge; Martinez, Sonia; Karataş, Timur; Bullo, Francesco (13. april 2004), »Coverage control for mobile sensing networks«, IEEE Transactions on Robotics and Automation, 20 (2): 243–255, doi:10.1109/TRA.2004.824698, ISSN 2374-958X, S2CID 2022860
• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2008), »7.4 Farthest-Point Voronoi Diagrams«, Computational Geometry (3. izd.), Springer-Verlag, ISBN 978-3-540-77974-2 – vsebuje opis algoritma.
• Dirichlet, Gustav Lejeune (1850), »Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen«, Journal für die Reine und Angewandte Mathematik, 1850 (40): 209–227, doi:10.1515/crll.1850.40.209, S2CID 199546675
• Edelsbrunner, Herbert (2012) [1987], »13.6 Power Diagrams«, Algorithms in Combinatorial Geometry, (EATCS Monographs on Theoretical Computer Science), zv. 10, Springer-Verlag, str. 327–328, ISBN 9783642615689
• Fanfoni, Massimo; Placidi, Ernesto; Arciprete, Fabrizio; Orsini, Elena; Patella, Fulvia; Balzarotti, Adalberto (2007), »Sudden nucleation versus scale invariance of InAs quantum dots on GaAs«, Physical Review B, 75 (24): 245312, Bibcode:2007PhRvB..75x5312F, doi:10.1103/PhysRevB.75.245312, ISSN 1098-0121, S2CID 120017577
• Feinstein, Joseph; Shi, Wentao; Ramanujam, J.; Brylinski, Michal (2021), Ballante, Flavio (ur.), »Bionoi: A Voronoi Diagram-Based Representation of Ligand-Binding Sites in Proteins for Machine Learning Applications«, Protein-Ligand Interactions and Drug Design, (Methods in Molecular Biology) (v angleščini), New York, NY: Springer US, zv. 2266, str. 299–312, doi:10.1007/978-1-0716-1209-5_17, ISBN 978-1-0716-1209-5, PMID 33759134, S2CID 232338911
• Hölscher, Tonio; Krömker, Susanne; Mara, Hubert (2020), »Der Kopf Sabouroff in Berlin: Zwischen archäologischer Beobachtung und geometrischer Vermessung«, Gedenkschrift für Georgios Despinis (v nemščini), Atene, Grčija: Muzej Benaki
• Hui, Li; Kang, Li; Taehyong, Kim; Aidong, Zhang; Murali, Ramanathan (Marec 2012), Baskurt, Atilla M.; Sitnik, Robert (ur.), »Spatial Modeling of Bone Microarchitecture«, Three-Dimensional Image Processing (3Dip) and Applications Ii, 8290: 82900P, Bibcode:2012SPIE.8290E..0PL, doi:10.1117/12.907371, S2CID 1505014
• Johnson, Steven (19. oktober 2006), The Ghost Map: The Story of London's Most Terrifying Epidemic — and How It Changed Science, Cities, and the Modern World, Penguin Publishing Group, str. 187, ISBN 978-1-101-15853-1, pridobljeno 16. oktobra 2017
• Kasim, Muhammad Firmansyah (1. januar 2017), »Quantitative shadowgraphy and proton radiography for large intensity modulations«, Physical Review E, 95 (2): 023306, arXiv:1607.04179, Bibcode:2017PhRvE..95b3306K, doi:10.1103/PhysRevE.95.023306, PMID 28297858, S2CID 13326345
• Klein, Rolf (1989), »Abstract Voronoi diagrams and their applications«, Computational Geometry and its Applications, (Lecture Notes in Computer Science), zv. 333, Springer, str. 148–157, doi:10.1007/3-540-50335-8_31, ISBN 978-3-540-52055-9
• Löbl, Matthias C.; Zhai, Liang; Jahn, Jan-Philipp; Ritzmann, Julian; Huo, Yongheng; Wieck, Andreas D.; Schmidt, Oliver G.; Ludwig, Arne; Rastelli, Armando; Warburton, Richard J. (3. oktober 2019), »Correlations between optical properties and Voronoi-cell area of quantum dots«, Physical Review B, 100 (15): 155402, arXiv:1902.10145, Bibcode:2019PhRvB.100o5402L, doi:10.1103/physrevb.100.155402, ISSN 2469-9950, S2CID 119443529
• 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, str. 333–, ISBN 978-0-470-87001-3
• Lopez, Clélia; Zhao, Chuan-Lin; Magniol, Stéphane; Chiabaut, Nicolas; Leclercq, Ludovic (28. februar 2019), »Microscopic Simulation of Cruising for Parking of Trucks as a Measure to Manage Freight Loading Zone«, Sustainability, 11 (5): 1276, doi:10.3390/su11051276, ISSN 2071-1050
• Mitchell, Tom Michael (1997), Machine Learning (mednarodna izd.), McGraw-Hill, str. 233, COBISS 3792935, ISBN 978-0-07-042807-2
• Miyamoto, Satoru; Moutanabbir, Oussama; Haller, Eugene E.; Itoh, Kohei M. (2009), »Spatial correlation of self-assembled isotopically pure Ge/Si(001) nanoislands«, Physical Review B, 79 (165415): 165415, Bibcode:2009PhRvB..79p5415M, doi:10.1103/PhysRevB.79.165415, ISSN 1098-0121, S2CID 13719907
• Mulheran, Paul A.; Blackman, John A. (15. april 1996), »Capture zones and scaling in homogeneous thin-film growth«, Physical Review B (Condensed Matter), 53 (15): 10261–10267, Bibcode:1996PhRvB..5310261M, doi:10.1103/PhysRevB.53.10261, PMID 9982595
• Niu, Hanlin; Savvaris, Al; Tsourdos, Antonios; Ji, Ze (24. januar 2019), »Voronoi-visibility roadmap-based path planning algorithm for unmanned surface vehicles« (PDF), Journal of Navigation, 72 (4): 850–874, doi:10.1017/S0373463318001005, ISSN 0373-4633, S2CID 67908628
• Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (2000), Spatial Tessellations – Concepts and Applications of Voronoi Diagrams (2. izd.), John Wiley, COBISS 9520729, ISBN 978-0-471-98635-5
• Pimpinelli, Alberto; Tumbek, Levent; Winkler, Adolf (2014), »Scaling and Exponent Equalities in Island Nucleation: Novel Results and Application to Organic Films«, The Journal of Physical Chemistry Letters, 5 (6): 995–998, doi:10.1021/jz500282t, PMC 3962253, PMID 24660052
• Reem, Daniel (2009), »An algorithm for computing Voronoi diagrams of general generators in general normed spaces«, Proceedings of the Sixth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2009): 144–152, doi:10.1109/ISVD.2009.23, ISBN 978-1-4244-4769-5
• Reem, Daniel (2011), »The geometric stability of Voronoi diagrams with respect to small changes of the sites«, Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG): 254–263, arXiv:1103.4125, Bibcode:2011arXiv1103.4125R, doi:10.1145/1998196.1998234, ISBN 9781450306829, S2CID 14639512
• Rong, Guodong; Tan, Tiow Seng (2006), »Jump flooding in GPU with applications to Voronoi diagram and distance transform« (PDF), v Olano, Marc; Séquin, Carlo H. (ur.), Proceedings of the 2006 Symposium on Interactive 3D Graphics, SI3D 2006, March 14-17, 2006, Redwood City, California, USA, ACM, str. 109–116, doi:10.1145/1111411.1111431
• Sanchez-Gutierrez, Daniel; Tozluoglu, Melda; Barry, Joseph D.; Pascual, Albero; Mao, Yanlan; Escudero, Luis M. (4. januar 2016), »Fundamental physical cellular constraints drive self-organization of tissues«, The EMBO Journal, 35 (1): 77–88, doi:10.15252/embj.201592374, ISSN 0261-4189, PMC 4718000, PMID 26598531
• Sen, Zekai (2016), »2.8.1 Delaney, Varoni, and Thiessen Polygons«, Spatial Modeling Principles in Earth Sciences (2. izd.), Springer, str. 57–, ISBN 978-3-319-41758-5
• Shenwai, Tanushree (18. november 2021), »A Novel Deep Learning Technique That Rebuilds Global Fields Without Using Organized Sensor Data«, MarkTechPost (v ameriški angleščini), pridobljeno 5. decembra 2021
• Singh, Kushagra; Sadeghi, Farshid; Correns, Martin; Blass, Toni (december 2019), »A microstructure based approach to model effects of surface roughness on tensile fatigue«, International Journal of Fatigue, 129: 105229, doi:10.1016/j.ijfatigue.2019.105229, ISSN 0142-1123, S2CID 202213370{{citation}}: Vzdrževanje CS1: samodejni prevod datuma (povezava)
• Skyum, Sven (18. februar 1991), »A simple algorithm for computing the smallest enclosing circle«, Information Processing Letters, 37 (3): 121–125, doi:10.1016/0020-0190(91)90030-L – vsebuje preprost algoritem za računanje Voronojevega diagrama najoddaljenejše točke.
• Springel, Volker (2010), »E pur si muove: Galilean-invariant cosmological hydrodynamical simulations on a moving mesh«, MNRAS, 401 (2): 791–851, arXiv:0901.4107, Bibcode:2010MNRAS.401..791S, doi:10.1111/j.1365-2966.2009.15715.x, S2CID 119241866
• Teruel, Enrique; Aragues, Rosario; López-Nicolás, Gonzalo (april 2021), »A Practical Method to Cover Evenly a Dynamic Region With a Swarm«, IEEE Robotics and Automation Letters, 6 (2): 1359–1366, doi:10.1109/LRA.2021.3057568, ISSN 2377-3766, S2CID 232071627{{citation}}: Vzdrževanje CS1: samodejni prevod datuma (povezava)
• Thiessen, Alfred Henry (1. julij 1911), »Precipitation averages for large areas«, Monthly Weather Review, 39 (7): 1082–1084, doi:10.1175/1520-0493(1911)39<1082b:PAFLA>2.0.CO;2, ISSN 0027-0644
• Tran, Quoc Thai; Tainar, David; Safar, Maytham (2009), »Reverse k Nearest Neighbor and Reverse Farthest Neighbor Search on Spatial Networks«, v Hameurlain, Abdelkader; Küng, Josef; Wagner, Roland (ur.), Transactions on Large-Scale Data- and Knowledge-Centered Systems I, (Lecture notes in computer science), zv. 5740, str. 357, COBISS 35429981, ISBN 978-3-642-03721-4
• Voronoï, Georges (1908a), »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.« (PDF), Journal für die Reine und Angewandte Mathematik, 1908 (133): 97–178, doi:10.1515/crll.1908.133.97, S2CID 116775758
• Voronoï, Georges (1908b), »Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs.« (PDF), Journal für die Reine und Angewandte Mathematik, 1908 (134): 198–287, doi:10.1515/crll.1908.134.198, S2CID 118441072
• Watson, David F. (1981), »Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes«, The Computer Journal, 24 (2): 167–172, doi:10.1093/comjnl/24.2.167

Zunanje povezave

• Weisstein, Eric Wolfgang. »Voronoi Diagram«. MathWorld.
• Voronoi Diagrams v programski knjižnici algoritmov računalniške keometrije CGAL (Computational Geometry Algorithms Library) (angleško)