Voronojev diagram

Iz Wikipedije, proste enciklopedije
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.[1] Imenuje se tudi Voronojeva teselacija (~ pokritje, ~ tlakovanje), Voronojeva dekompozicija, Voronojeva particija ali Dirichletova teselacija (po Johannu Petru Gustavu Lejeunu Dirichletu).[2][3][4][5] 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.[6] Voronojevi diagrami se praktično in teoretično uporabljajo na številnih področjih, predvsem v znanosti in tehnologiji, pa tudi v likovni umetnosti.[7][8]

Najpreprostejši primer[uredi | uredi kodo]

V najpreprostejšem primeru, prikazanem na prvi sliki, je končna množica točk v evklidski ravnini. V tem primeru je vsako mesto preprosto točka in njena ustrezna Voronojeva celica je sestavljena iz vsake točke v evklidski ravnini, katere razdalja do točke je manjša ali enaka njeni razdalji do katere koli druge točke . Vsaka taka celica je pridobljena iz presečišča polprostorov in je torej (konveksni) polieder.[9] 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[uredi | uredi kodo]

Naj je metrični prostor s funkcijo razdalje . naj je množica indeksov in n-terica (urejena zbirka) nepraznih podmnožic (mest) v prostoru . Voronojeva celica ali Voronojevo območje , povezano z mestom je množica vseh točk v , katerih razdalja do ni večja od njihove razdalje do drugih mest , kjer je poljubni indeks, različen od . Z drugimi besedami, če označuje razdaljo med točko in podmnožico , potem velja:

Voronojev diagram je preprosto trojica celic . 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 je povezan z generatorsko točko . Naj je množica vseh točk v evklidskem prostoru. naj je točka, ki generira Voronojevo območje , , ki genrira in , ki generira in tako naprej. , and so on. Potem, kot je navedeno v Tran; Tainar; Safar (2009)[10], 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[uredi | uredi kodo]

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 dane trgovine 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:

ali z manhattansko razdaljo:

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

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

Značilnosti[uredi | uredi kodo]

  • 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.[11] 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.[12] 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[uredi | uredi kodo]

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.[1] 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[uredi | uredi kodo]

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.

Za množico točk z v diskretni množici in v diskretni množici se dobi pravokotne ploščice s točkami, ki niso nujno v njihovih središčih.

Voronojevi diagrami višjih redov[uredi | uredi kodo]

Čeprav je normalna Voronojeva celica definirana kot množica točk, najbližjih eni točki v množici , je Voronojeva celica n-tega reda definirana kot množica točk, ki ima določeno množico n točk v 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 se začne z diagramom reda in vsaka celica, generirana z , se zamenja z Voronojevim diagramom, generiranim na množici .

Voronojev diagram najoddaljenejše točke[uredi | uredi kodo]

Za dano množico n točk se Voronojev diagram reda imenuje Voronojev diagram najoddaljenejše točke.

Za dano množico točk Voronojev diagram najoddaljenejše točke deli ravnino na celice v katerih je ista točka najoddaljenejša točka. Točka ima celico v Voronojevem diagramu najoddaljenejše točke, če in samo če je oglišče konveksne ogrinjače . Naj bo konveksna ogrinjača . Potem je Voronojev diagram najoddaljenejše točke podrazdelitev ravnine na celic, po eno za vsako točko v z značilnostjo, da točka leži v celici, ki ustreza mestu , če in samo če velja za vsako točko s , kjer je evklidska razdalja med dvema točkama in .[13][14]

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.[15]

Posplošitve in variacije[uredi | uredi kodo]

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.[16]

Voronojev diagram n točk v d-razsežnem prostoru ima lahko 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.[17]

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[uredi | uredi kodo]

Meteorologija in hidrologija[uredi | uredi kodo]

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 , ki se dotika točke postaje, je znano kot vplivno območje postaje. Povprečno količino padavin se izračuna po formuli

Glej tudi: Delaunayeva triangulacija#Uporabe

Humanistika[uredi | uredi kodo]

Naravoslovje[uredi | uredi kodo]

Voronojevo pokritje nastane z radialno rastjo iz semena navzven.

Zdravje[uredi | uredi kodo]

  • v medicinski diagnostiki se lahko uporabijo modeli mišičnih tkiv na podlagi Voronojevih diagramov za zaznavo nevromuskulaturnih bolezni.[22]
  • 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.[26]

Inženirstvo[uredi | uredi kodo]

Geometrija[uredi | uredi kodo]

Informatika[uredi | uredi kodo]

Nauk o državi in načrtovanje[uredi | uredi kodo]

  • 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.[41]

Pekarstvo[uredi | uredi kodo]

  • 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[uredi | uredi kodo]

Polravnini in sta ločeni s simetralo daljice.

V preprostem algoritmu simetrala daljice povezuje nek poljubni par točk in . Takšna simetrala razdeli ravnino na dve polravnini in , pri čemer je Voronojevo območje v celoti v eni od njiju, območje točke pa v drugi. Voronojevo območje točke sovpada s presečiščem vseh takih polravnin :

Tako se rešitev problema zmanjša na izračun takega presečišča za vsako točko . Algoritem je mogoče implementirati z zahtevnostjo .[42]

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 .

Boyer-Watsonov algoritem, algoritem za generiranje Delaunayeve triangulacije v poljubni razsežnosti z zahtevnostjo od do , 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.[43][44]

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 je razdeljena na dve podmnožici in , za vsako od njih pa je izdelan Voronojev diagram, nato pa se dobljena diagrama združita v enega. Razdelitev množice 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 in je mogoče izvesti v času , tako da je zahtevnost takšnega algoritma enaka .

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

  1. 1,0 1,1 Voronoï (1908a) in Voronoï (1908b).
  2. Burrough idr. (2015).
  3. Longley idr. (2005).
  4. Sen (2016).
  5. Dirichlet (1850).
  6. Thiessen (1911).
  7. Aurenhammer (1991).
  8. Okabe idr. (2000).
  9. Boyd; Vandenberghe (2004).
  10. Tran; Tainar; Safar (2009).
  11. Reem (2009).
  12. Reem (2011).
  13. 13,0 13,1 de Berg idr. (2008).
  14. Skyum (1991).
  15. Biedl idr. (2016).
  16. Edelsbrunner (2012).
  17. Arya; Malamatos; Mount (2002).
  18. Hölscher; Krömker; Mara (2020).
  19. Bayer; Kunkel; Mara (2020). GigaMesh Tutorial 10 - Voronoi Cells & Geodesic Distances - Sabouroff head na YouTubu. Analiza uporabe programja GigaMesh Software Framework, kot je opisana v Hölscher; Krömker; Mara (2020).
  20. Bock idr. (2009).
  21. Hui idr. (2012).
  22. 22,0 22,1 Sanchez-Gutierrez idr. (2016).
  23. Feinstein idr. (2021).
  24. Springel (2010).
  25. Kasim (2017).
  26. Johnson (2006).
  27. Mulheran; Blackman (1996).
  28. Pimpinelli; Tumbek; Winkler (2014).
  29. Fanfoni idr. (2007).
  30. Miyamoto idr. (2009).
  31. Löbl idr. (2019).
  32. "GOLD COAST CULTURAL PRECINCT" (angleščina). ARM Architecture. Arhivirano iz prvotnega spletišča dne 7. julija 2016. Pridobljeno dne 15. oktobra 2022.
  33. Lopez idr. (2019).
  34. Singh idr. (2019).
  35. Niu idr. (2019).
  36. Cortés idr. (2004).
  37. Teruel; Aragues; López-Nicolás (2021).
  38. Mitchell (1997).
  39. Shenwai (2021).
  40. Arhivirano na Ghostarchive in Wayback Machine: "Mark DiMarco: User Interface Algorithms [JSConf2014]" – via www.youtube.com.
  41. "School zones". Victorian Government Department of Education and Training (angleščina). Arhivirano iz prvotnega spletišča dne 2020-08-11. Pridobljeno dne 24. avgusta 2020.
  42. "Диаграмма Вороного в 2D". MAXimal (ruščina). 26. januar 2009. Arhivirano iz prvotnega spletišča dne 8. junija 2021. Pridobljeno dne 8. junija 2021.
  43. Rong; Tan (2006).
  44. "Jump Flooding". Shadertoy (angleščina). 24. februar 2016.

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]