Voronojev dijagram

U matematici, Voronojev dijagram je particionisanje ravni u oblasti zasnovano na udaljenosti od tačaka iz posebnog podskupa ravni. Taj skup tačaka (zvanih semena, položaji, ili generatori) je određen unapred, i za svaki generator postoji odgovarajuća oblast koja se sastoji od svih tačaka koje su bliže tom generatoru nego bilo kom drugom. Ove oblasti se nazivaju Voronojeve ćelije.

Nazvane su po Georgiju Voronoju, i još se nazivaju Voronojeva teselacija, Voronojeva dekompozicija, Voronojevo particionisanje, ili Dirihleova teselacija (po Johan Peter Gustav Ležen Dirihle). Voronojevi dijagrami imaju praktičnu i teorijsku upotrebu u velikom broju oblasti, pre svega u nauci i tehnologiji, ali i likovnoj umetnosti.^[1]^[2]

Najjednostavniji slučaj[uredi | uredi izvor]

U najjednostavnijem i najpoznatijem slučaju (prikazano na prvoj slici), imamo konačan skup tačaka {p₁, …, p_n} u Euklidskoj ravni. U ovom slučaju svaki generator je jednostavna tačka i njene odgovarajuće Voronojeve ćelije (poznate i kao Voronojeve oblasti ili Dirihleove ćelije) R_k se sastoji od svake tačke čija je udaljenost do p_k manja ili jednaka od udaljenosti do bilo kog drugog generatora. Svaka takva ćelija je dobijena kao presek poluprostora, pa je stoga konveksan mnogougao. Segmenti Voronojevog dijagrama su sve tačke u ravni koje su podjednako udaljene od dva najbliža generatora. Voronojeva temena su tačke podjednako udaljene od tri (ili više) generatora.

Formalna definicija[uredi | uredi izvor]

Neka je $\scriptstyle X$ prostor (neprazan skup) sa metrikom $\scriptstyle d$ . Neka je $\scriptstyle K$ skup indeksa i neka je $\scriptstyle (P_{k})_{k\in K}$ n-torka (uređena kolekcija) nepraznih podskupova (generatora) u prostoru $\scriptstyle X$ . Voronojeva ćelija, ili Voronojeva oblast, $\scriptstyle R_{k}$ , koja odgovara generatoru $\scriptstyle P_{k}$ je skup svih tačaka u $\scriptstyle X$ čija udaljenost do $\scriptstyle P_{k}$ nije veća od udaljenosti do drugih generatora $\scriptstyle P_{j}$ , gde je $\scriptstyle j$ bilo koji indeks različit od $\scriptstyle k$ . Drugim rečima, ako $\scriptstyle d(x,\,A)\;=\;\inf\{d(x,\,a)\mid a\,\in \,A\}$ označava rastojanje između tačke $\scriptstyle x$ i podskupa $\scriptstyle A$ , onda

R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{for all}}\;j\neq k\}

Voronojev dijagram je jednostavno n-torka ćelija $\scriptstyle (R_{k})_{k\in K}$ . U principu neki od generatora se mogu presecati i čak poklapati (primer je opisan ispod za generatore koji predstavljaju prodavnice), ali obično se pretpostavlja da su razdvojeni. Takođe, beskonačno mnogo generatora je dozvoljeno u definiciji (ima primenu u geometriji brojeva i kristalografiji), ali opet u mnogim slučajevima se razmatra samo konačan broj generatora.

U posebnom slučaju kada je prostor konačno-dimenzioni Euklidski prostor, svaki generator je tačka, ima konačno mnogo tačaka i sve su različite, onda su Voronojeve ćelije koveksni politopi i mogu biti predstavljene pomoću temena, ivica, 2-dimenzionih strana, itd. Nekada je tako indukovana struktura Voronojev dijagram, međutim, generalno Voronojeve ćelije ne moraju biti ni konveksne ni povezane.

U uobičajenom Eukliskom prostoru, možemo ponovo napisati formalnu definiciju. Svakom Voronojevom mnogouglu $\scriptstyle R_{k}$ odgovara generatorna tačka $\scriptstyle P_{k}$ . Neka je $\scriptstyle X$ skup svih tačaka u euklidskom prostoru. Neka je $\scriptstyle P_{1}$ tačka koja generiše Voronojevu oblast $\scriptstyle R_{1}$ , $\scriptstyle P_{2}$ generiše $\scriptstyle R_{2}$ , $\scriptstyle P_{3}$ generiše $\scriptstyle R_{3}$ , i tako dalje. Tada po Tran et al^[3] "sve lokacije u Voronojevom mnogouglu su bliže generatornoj tački u tom mnogouglu nego bilo kojoj drugoj generatornoj tački u Euklidskoj ravni".

Ilustracija[uredi | uredi izvor]

Kao jednostavnu ilustraciju, razmotrimo grupu prodavnica u nekom gradu. Pretpostavimo da želimo da procenimo broj kupaca za datu prodavnicu. Ako je sve ostalo isto (cena, proizvodi, kvalitet usluge, itd.), razumno je pretpostaviti da kupci biraju svoju prodavnicu na osnovu udaljenosti: otići će u prodavnicu koja im je najbliža. U ovom slučaju Voronojeva ćelija $\scriptstyle R_{k}$ za datu prodavnicu $\scriptstyle P_{k}$ može biti iskorišćena za grubu procenu broja potencijalnih kupaca koji dolaze u tu prodavnicu.

Do sada smo pretpostavljali da je rastojanje između tačaka mereno Euklidskim rastojanjem:

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

Međutim, ako razmotrimo slučaj kada kupci odlaze u prodavnice vozilom i saobraćajne trake su paralelne $x$ i $y$ osama, kao na Menhetnu, tada je realističnija metrika $\ell _{1}$ , data sa $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|$ .

Voronojev dijagram sa 20 tačaka u dve različite metrike

Euklidsko rastojanje

Menhetn rastojanje

Osobine[uredi | uredi izvor]

Dualni graf za Voronojev dijagram (u slučaju Euklidskog prostora sa tačkama generatorima) odgovara Delonijevoj triangulaciji za isti skup tačaka.
Najbliži par tačaka odgovara dvema susednim ćelijama u Voronojevom dijagramu
Ako je data grupa različitih tačaka u ravni, tada su dve tačke susedne u konveksnom omotaču ako i samo ako njihove Voronojeve ćelije dele beskonačno dugu stranicu.
Ako je prostor normiran i udaljenost do svakog generatora je dostižna (npr. kada je generator kompaktan skup ili zatvorena kugla), onda se svaka Voronojeva ćelija može predstaviti kao unija segmenata linija koje potiču iz generatora.^[4]

Ovo svojstvo ne mora nužno da važi ukoliko udaljenost nije dostižna.

U relativno opštim uslovima (ako je prostor beskonačno dimenzioni ravnomerno konveksni prostor, može biti beskonačno mnogo generatora, itd) Voronojeve ćelije pokazuju određeno svojstvo stabilnosti: male promene u obliku generatora (npr. promene izazvane translacijom ili distorzijom) proizvode male promene oblika Voronojevih ćelija. Ovo je geometrijska stabilnost Voronojevih dijagrama.^[5] Ovo svojstvo ne mora da važi u opštem slučaju, čak iako je prostor dvodimenzioni (ali ne ravnomerno konveksan, i posebno neeuklidski) i generatori su tačke.

Istorija i istraživanja[uredi | uredi izvor]

Neformalna upotreba Voronojevih dijagrama se može sresti još kod Dekarta 1644. Dirihle je koristio 2-dimenzione i 3-dimenzione Voronojeve dijagrame u svojoj studiji o kvadratnim formama 1850. Britanski fizičar Džon Snou je koristio Voronojeve dijagrame 1854 da ilustruje kako je većina ljudi koja je umrla u epidemiji kolere u Sohou 1854 živela bliže vodenoj pumpi u Broad ulici nego bilo kojoj drugoj pumpi. Voronojevi dijagrami su nazvani po Ukrajinskom matematičaru Georgiju Fedosijeviču Voronoju koji je proučavao i definisao n-dimenzioni slučaj 1908. Voronojevi dijagrami koji se koriste u geofizici i meteorologiji za analizu prostorno distribuiranih podataka (kao što je merenje padavina) se nazivaju Tiesenovi poligoni po Američkom metereologu Alfredu H. Tiesenu. U fizici kondenzovane materije takve teselacije su poznate i kao Wigner–Seitz ćelije. Druga ekvivalentna imena za ovaj koncept (ili njegov poseban slučaj) : Voronojevi poliedri, Voronojevi poligoni, domeni uticaja, Voronojeva dekompozicija, Dirihleova teselacija.

Voronojevi dijagrami višeg reda[uredi | uredi izvor]

Iako je normalna Voronojeva ćelija definisana kao skup tačaka najbližih jednoj određenoj tački u S, Voronojeva ćelija n-og reda je definisana kao skup tačaka koje imaju određen skup od n tačaka u S kao svojih n najbližih komšija. Voronojevi dijagrami višeg reda takođe dalje dele prostor.

Voronojevi dijagrami višeg reda mogu biti definisani rekurzivno. Za generisanje Voronojevog dijagrama n-og reda iz skupa S, počinje se sa dijagramom(n − 1)-og reda i zamenjuje svaka ćelija generisana sa X = {x₁, x₂, ..., x_n−1} sa Voronojevim dijagramom generisanim skupom S − X.

Voronojev dijagram najudaljenije tačke[uredi | uredi izvor]

Za skup od n tačaka Voronojev dijagram (n − 1)-og reda se zove Voronojev dijagram najudaljenije tačke.

Za dati skup tačaka P = {p₁, p₂, ..., p_n} Voronojev dijagram najudaljenije tačke deli ravan na ćelije u kojima je ista tačka iz P najudaljenija. Primetimo da tačka iz P ima ćeliju u Voronojevom dijagramu najudaljenije tačke ako i samo ako je teme konveksnog omotača od P. Prema tome neka je H = {h₁, h₂, ..., h_k} konveksni omotač od P definišemo Voronojev dijagram najudaljenije tačke kao podelu ravni na k ćelija, jednu za svaku ćeliju u H, sa osobinom da tačka q leži u ćeliji koja odgovara generatoru h_i ako i samo ako dist(q, h_i) > dist(q, p_j) za svako p_j ∈ S i h_i ≠ p_j. gde je dist(p, q) Euklidsko rastojanje između dve tačke p and q.^[6]^[7]

Generalizacija i varijacije[uredi | uredi izvor]

Kao što je rečeno u definiciji, Voronojeve ćelije mogu biti definisane i za druge metrike osim Euklidske. Međutim može se desiti da granice Voronojevih ćelija mogu biti komplikovanije nego u Euklidskom slučaju, jer se može desiti da ekvidistantno mesto za dve tačke ne bude potprostor dimenzije 1, čak ni u 2-dimenzionom slučaju.

približni Voronojev dijagram skupa tačaka. Primetite izmešane boje na granicama Voronojevih ćelija.

Težinski Voronojev dijagram je onaj u kom funkcija para tačaka koja definiše Voronojevu ćeliju je funkcija udaljenosti modifikovana za težinu dodeljenu generatornim tačkama. Za razliku od slučaja kada je Voronojeva ćelija definisana koristeći metriku, u ovom slučaju neke od Voronojevih ćelija mogu biti prazne.

Voronojev dijagrram sa n tačaka u d-dimenzionom prostoru zahteva $\scriptstyle O\left(n^{\left\lceil {\frac {1}{2}}d\right\rceil }\right)$ prostora za skladištenje. Zato, Voronojevi dijagrami često nisu ostvarljivi za d > 2. Alternativa je da se koriste približni Voronojevi dijagrami, gde Voronojeve ćelije imaju nejasne granice, koje mogu biti aproksimirane.^[8] Druga alternativa je kada su svi generatori nejasni krugovi kao rezultat i ćelije postaju nejasne.^[9]

Voronojevi dijagrami su takođe povezani i sa drugim geometrijskim strukturama koje imaju široku primenu u kompjuterskim aplikacijama. Pored tačaka, neki dijagrami koriste i linije i poligone kao generatore. Taj princip koriste npr. navigacione mreže koje služe za pronalaženje puteva u velikim prostorima. Navigaciona mreža može biti i generalizovana da podrži 3D okruženja kao što su aerodromi ili zgrade sa više spratova.^[10]

Primene[uredi | uredi izvor]

U geometriji, Voronojevi dijagrami se mogu koristiti za pronalaženje najvećeg praznog kruga usred skupa tačaka i u okolnom poligonu; npr. izgradnja novog supermarketa što dalje od postojećih, ali u istom gradu.
U epidemiologiji, Voronojevi dijagrami mogu biti korišćeni da prikažu korelaciju izvora infekcija u epidemijama. Jedna od ranih primena Voronojevih dijagrama je bila implementirana od strane Džona Snoa za proučavanje epidemije kolere 1854 u Sohou u Engleskoj. On je prikazao odnos između oblasti na mapi Londona koristeći određenu pumpu za vodu, i oblasti sa najviše smrti za vreme epidemije.
Struktura podataka za lokaciju tačke može biti formirana na osnovu Voronojevog dijagrama radi odgovora na upite za pretraživanje najbližeg suseda gde se traži objekat koji je najbliži datoj tački. Pretraživanje najbližeg suseda ima brojne primene. Na primer, ukoliko nam je potrebno da pronađemo najbližu bolnicu, ili najsličniji objekat u bazi podataka.
Voronojevi dijagrami zajedno sa Voronojevim dijagramima najudaljenije tačke se koriste kao efikasni algoritmi za izračunavanje okruglosti skupa tačaka.^[11]
U hidrologiji, Voronojevi dijagrami se koriste za izračunavanje količine padavina na određenom području, bazirano na seriji merenja u određenim tačkama. Kada se koriste na ovaj način, obično se nazivaju Tiesenovi poligoni.
U ekologiji, Voronojevi dijagrami se koriste za proučavanje trendova rasta šuma i mogu biti takođe korišćeni u razvoju modela za predviđanje šumskih požara.
U rudarstvu, Voronojevi dijagrami se koriste za procenu rezervi vrednih materijala, minerala ili drugih resursa. Istraživačke bušotine se koriste kao skup tačaka u Voronojevim dijagramima.
U proučavanju navigacije robota, Voronojevi dijagrami se koriste za pronalaženje čiste putanje. Ako su tačke prepreke, onda su ivice dijagrama putanje najudaljenije od prepreka.

Vidi još[uredi | uredi izvor]

Fortunov algoritam, O(n log(n)) algoritam za generisanje Voronojevog dijagrama iz skupa tačaka u ravni

Reference[uredi | uredi izvor]

^ Aurenhammer, Franz (1991). „Voronoi diagrams—a survey of a fundamental geometric data structure”. ACM Computing Surveys. 23 (3): 345—405. S2CID 4613674. doi:10.1145/116873.116880.
^ Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (1991). Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (2nd izd.). Wiley. ISBN 978-0-471-98635-5.
^ Q.T.Tran; D.Tainar; M.Safar (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems. str. 357. ISBN 978-3-642-03721-4.
^ Reem, Daniel (2009). „An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces”. 2009 Sixth International Symposium on Voronoi Diagrams. str. 144—152. ISBN 978-1-4244-4769-5. S2CID 24930500. doi:10.1109/ISVD.2009.23.
^ Reem, Daniel (2011). „The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites”. Proceedings of the twenty-seventh annual symposium on Computational geometry. str. 254—263. ISBN 9781450306829. S2CID 14639512. arXiv:1103.4125 . doi:10.1145/1998196.1998234.
^ Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third izd.). Springer-Verlag. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.
^ Skyum, Sven (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.
^ S. Arya, T. Malamatos, and D. M. Mount,Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002). pp. 721–730.
^ Jooyandeh, Mohammadreza; Mohades, Ali; Mirzakhah, Maryam (2009). „Uncertain Voronoi Diagram”. Information Processing Letters. Elsevier. 109 (13): 709—712. doi:10.1016/j.ipl.2009.03.007.
^ van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland (2011), Navigation Meshes for Realistic Multi-Layered Environments (PDF), International Conference on Intelligent Robots and Systems, IEEE/RSJ, str. 3526—3532
^ Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third izd.). Springer-Verlag. ISBN 978-3-540-77974-2. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.

Literatura[uredi | uredi izvor]

Q.T.Tran; D.Tainar; M.Safar (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems. str. 357. ISBN 978-3-642-03721-4.
Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third izd.). Springer-Verlag.
G. Lejeune Dirichlet (1850). „Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen”. Journal für die Reine und Angewandte Mathematik. 40: 209—227.
Voronoi, Georgy (1908). „Nouvelles applications des paramètres continus à la théorie des formes quadratiques”. Journal für die Reine und Angewandte Mathematik. 133 (133): 97—178. S2CID 116775758. doi:10.1515/crll.1908.133.97.
Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Spatial Tessellations – Concepts and Applications of Voronoi Diagrams (2nd izd.). John Wiley. ISBN 978-0-471-98635-5.
Aurenhammer, Franz (septembar 1991). „Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure”. ACM Computing Surveys. 23 (3): 345—405. S2CID 4613674. doi:10.1145/116873.116880.
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). str. 144—152. ISBN 978-1-4244-4769-5. doi:10.1109/ISVD.2009.23.
Daniel Reem (2011). The geometric stability of Voronoi diagrams with respect to small changes of the sites. Full version: Reem, Daniel (2011). „The geometric stability of Voronoi diagrams with respect to small changes of the sites”. arXiv:1103.4125 . , Extended abstract: Reem, Daniel (2011). „The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites”. Proceedings of the twenty-seventh annual symposium on Computational geometry. str. 254—263. ISBN 9781450306829. S2CID 14639512. arXiv:1103.4125 . doi:10.1145/1998196.1998234. .
Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, and Otfried (2000). Computational Geometry (2nd revised izd.). Springer-Verlag. ISBN 978-3-540-65620-3. Chapter 7: Voronoi Diagrams: pp. 147–163. Includes a description of Fortune's algorithm.
Klein, Rolf (1989). „Abstract voronoi diagrams and their applications”. Computational Geometry and its Applications. Lecture Notes in Computer Science. 333. Springer-Verlag. str. 148—157. ISBN 978-3-540-52055-9. doi:10.1007/3-540-50335-8_31.

Spoljašnje veze[uredi | uredi izvor]

[1] Aurenhammer, Franz (1991). „Voronoi diagrams—a survey of a fundamental geometric data structure”. ACM Computing Surveys. 23 (3): 345—405. S2CID 4613674. doi:10.1145/116873.116880.

[2] Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (1991). Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (2nd izd.). Wiley. ISBN 978-0-471-98635-5.

[Tran09-3] Q.T.Tran; D.Tainar; M.Safar (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems. str. 357. ISBN 978-3-642-03721-4.

[Reem_alg-4] Reem, Daniel (2009). „An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces”. 2009 Sixth International Symposium on Voronoi Diagrams. str. 144—152. ISBN 978-1-4244-4769-5. S2CID 24930500. doi:10.1109/ISVD.2009.23.

[Reem_geo_stable-5] Reem, Daniel (2011). „The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites”. Proceedings of the twenty-seventh annual symposium on Computational geometry. str. 254—263. ISBN 9781450306829. S2CID 14639512. arXiv:1103.4125 . doi:10.1145/1998196.1998234.

[berg2008-6] Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third izd.). Springer-Verlag. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.

[7] Skyum, Sven (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.

[8] S. Arya, T. Malamatos, and D. M. Mount,Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002). pp. 721–730.

[9] Jooyandeh, Mohammadreza; Mohades, Ali; Mirzakhah, Maryam (2009). „Uncertain Voronoi Diagram”. Information Processing Letters. Elsevier. 109 (13): 709—712. doi:10.1016/j.ipl.2009.03.007.

[10] van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland (2011), Navigation Meshes for Realistic Multi-Layered Environments (PDF), International Conference on Intelligent Robots and Systems, IEEE/RSJ, str. 3526—3532

[automatski_generisano1-11] Berg, Mark de; Kreveld, Marc van; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third izd.). Springer-Verlag. ISBN 978-3-540-77974-2. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Normativna kontrola
Međunarodne	FAST
Državne	Francuska BnF podaci Nemačka Izrael Sjedinjene Države
Ostale	IdRef