Voronojev diagram

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.Predloga:R Imenuje se tudi Voronojeva teselacija (~ pokritje, ~ tlakovanje), Voronojeva dekompozicija, Voronojeva particija ali Dirichletova teselacija (po Johannu Petru Gustavu Lejeunu Dirichletu).Predloga:R Predloga:R Predloga:R Predloga:R 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.Predloga:R Voronojevi diagrami se praktično in teoretično uporabljajo na številnih področjih, predvsem v znanosti in tehnologiji, pa tudi v likovni umetnosti.Predloga:R Predloga:R

Najpreprostejši primer

V najpreprostejšem primeru, prikazanem na prvi sliki, je končna množica točk ${p_{1}, \dots, 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.Predloga:R 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 $X$ metrični prostor s funkcijo razdalje $d$ . $K$ naj je množica indeksov in $(P_{k})_{k \in K}$ n-terica (urejena zbirka) nepraznih podmnožic (mest) v prostoru $X$ . Voronojeva celica ali Voronojevo območje $R_{k}$ , povezano z mestom $P_{k}$ je množica vseh točk v $X$ , katerih razdalja do $P_{k}$ ni večja od njihove razdalje do drugih mest $P_{j}$ , kjer je $j$ poljubni indeks, različen od $k$ . Z drugimi besedami, če $d (x, A) = \inf {d (x, a) ∣ a \in A}$ označuje razdaljo med točko $x$ in podmnožico $A$ , potem velja:

R_{k} = {x \in X ∣ d (x, P_{k}) \leq d (x, P_{j}) za vse j \neq k} .

Voronojev diagram je preprosto trojica celic $(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 $R_{k}$ je povezan z generatorsko točko $P_{k}$ . Naj je $X$ množica vseh točk v evklidskem prostoru. $P_{1}$ naj je točka, ki generira Voronojevo območje $R_{1}$ , $P_{2}$ , ki genrira $R_{2}$ in $P_{3}$ , ki generira $R_{3}$ in tako naprej. Potem, kot je navedeno v Tran; Tainar; Safar (2009)Predloga:R, 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 $R_{k}$ dane trgovine $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:

ℓ_{2} = d [(a_{1}, a_{2}), (b_{1}, b_{2})] = \sqrt{{(a_{1} - b_{1})}^{2} + {(a_{2} - b_{2})}^{2}}

ali z manhattansko razdaljo:

d [(a_{1}, a_{2}), (b_{1}, b_{2})] = | a_{1} - b_{1} | + | a_{2} - b_{2} | .

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

Predloga:Več slik

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.Predloga:R 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.Predloga:R 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.Predloga:R 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

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

Voronojev diagram najoddaljenejše točke

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

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

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.Predloga:R

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.Predloga:R

Voronojev diagram n točk v d-razsežnem prostoru ima lahko $O (n^{⌈ d / 2 ⌉})$ 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.Predloga:R

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 $(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 $\bar{P} = \frac{\sum A_{i} P_{i}}{\sum A_{i}}$ Predloga:Glej tudi

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.Predloga:R Predloga:R
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 Predloga:R in mikroarhitektura kosti.Predloga:R Voronojeva pokritja dejansko delujejo kot geometrijsko orodje za razumevanje fizičnih omejitev, ki poganjajo organizacijo bioloških tkiv.Predloga:R
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).Predloga:R 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.Predloga:R
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.Predloga:R

Zdravje

v medicinski diagnostiki se lahko uporabijo modeli mišičnih tkiv na podlagi Voronojevih diagramov za zaznavo nevromuskulaturnih bolezni.Predloga:R
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.Predloga:R

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.Predloga:R Predloga:R Predloga:R Predloga:R Predloga:R 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.Predloga:R
v urbanističnem načrtovanju se lahko Voronojevi diagrami uporabijo za ovrednotenje sistema Freight Loading Zone (območja nakladanja tovora).Predloga:R
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.Predloga:R
v robotiki nekatere strategije nadzora in algoritmi za načrtovanje poti sistemov z več roboti Predloga:R temeljijo na Voronojevem razdeljevanju okolja.Predloga:R Predloga:R

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.Predloga:R 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.Predloga:R
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 Predloga:R
pri razvoju uporabniških vmesnikov je mogoče Voronojeve vzorce uporabiti za izračun najboljšega stanja lebdenja za dano točko.Predloga:R

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.Predloga:R

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 algoritmu simetrala daljice povezuje nek poljubni par točk $p$ in $q$ . Takšna simetrala razdeli ravnino na dve polravnini $H_{p q}$ in $H_{q p}$ , pri čemer je Voronojevo območje $p$ v celoti v eni od njiju, območje točke $q$ pa v drugi. Voronojevo območje $V_{p}$ točke $p$ sovpada s presečiščem vseh takih polravnin $H_{p q}$ :

V_{p} = ⋂_{q \in S / {p}} H_{p q} .

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

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 $O (n \log n)$ .

Boyer-Watsonov algoritem, algoritem za generiranje Delaunayeve triangulacije v poljubni razsežnosti z zahtevnostjo od $O (n \log n)$ do $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.Predloga:R Predloga:R

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

Glej tudi

Predloga:Div col

Predloga:Div col end

Sklici

Predloga:Refbegin Predloga:Sklici Predloga:Refend

Viri

Predloga:Refbegin

Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat – vsebuje opis algoritma.
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat – vsebuje preprost algoritem za računanje Voronojevega diagrama najoddaljenejše točke.
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat
Predloga:Citat

Predloga:Refend

Zunanje povezave

Predloga:Kategorija v Zbirki

Predloga:MathWorld
Voronoi Diagrams v programski knjižnici algoritmov računalniške keometrije CGAL (Computational Geometry Algorithms Library) Predloga:In lang

Predloga:Normativna kontrola