thumb|right|20 naključnih točk v ravnini in njihove Voronojeve celice (večja različica spodaj) thumb|right|Thiessnovi mnogokotniki thumb|right|Fotografija nevronov (levo) in ustrezni Voronojev mozaik, zgrajen na podlagi njihovih centroidov (geometrijskih središč) Voronojev diagrám [voronójev ~], tudi voronoijev diagram 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 ukrajinskem 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 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. 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ž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. 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:
ali z manhattansko razdaljo:
Odgovarjajoča Voronojeva diagrama izgledata različno za različno metriko razdalje.
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 thumb|right|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 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.
thumb|right|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 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.