Voronojev diagrám je v matematikirazdeljevanjeravnine 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.
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ščapolprostorov 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 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žnievklidski 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. 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 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:
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.
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
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 pokritjepravilno – 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.
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
Č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
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 .
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.
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 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.
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
v dialektometriji se Voronojeve celice rabijo za prikaz domnevne jezikovne kontinuitete med merilnimi točkami.
Naravoslovje
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 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 medicinskidiagnostiki 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.
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 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 robotiki nekatere strategije nadzora in algoritmi za načrtovanje poti sistemov z večroboti temeljijo na Voronojevem razdeljevanju okolja.
Geometrija
podatkovno strukturolege 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.
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 povezavegrafa poti, ki so najbolj oddaljene od ovir (in teoretično morebitnih trkov).
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
V preprostem algoritmusimetrala 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.
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.
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 .
↑»School zones«. Victorian Government Department of Education and Training (v angleščini). Arhivirano iz prvotnega spletišča dne 11. avgusta 2020. Pridobljeno 24. avgusta 2020.
Edelsbrunner, Herbert (2012) , »13.6 Power Diagrams«, Algorithms in Combinatorial Geometry, (EATCS Monographs on Theoretical Computer Science), zv. 10, Springer-Verlag, str. 327–328, ISBN9783642615689
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, ISBN978-1-0716-1209-5, PMID33759134, S2CID232338911
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, S2CID1505014
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, ISSN2071-1050
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, ISBN978-1-4244-4769-5
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, ISSN0142-1123, S2CID202213370{{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.
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, COBISS35429981, ISBN978-3-642-03721-4
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
Wikimedijina zbirka ponuja več predstavnostnega gradiva o temi: Voronojev diagram.