Voronoi diagramm

Voronoi diagramm on matemaatika mõiste, mis tähendab pinna jagamist osadeks sellel asuvate punktide omavahelise kauguse arvestamise kaudu. Need algpunktid on varem defineeritud ning igale punktile kuulub piirkond, mis moodustub kõige lähemal asuvatest punktidest. Iga punktiga määratud piirkonda nimetatakse Voronoi rakuks. Mingisuguse hulga punktide Voronoi diagramm on duaalne selle hulga Delaunay triangulatsiooniga. Piltlikult on tegemist joonisega, milles on võetud kaks üksteisele lähedal asuvat punkti ning kus on joonistatud ristsirge nende kahe punkti vahele. Kõik diagrammi joontel asuvad punktid on võrdsel kaugusel selle allikpunktidest.

Eukleidiline Voronoi diagramm

Voronoi diagrammi nimi on tulnud Georgi Voronoi järgi ning seda nimetatakse ka Voronoi mosaiigiks, Voronoi dekompositsiooniks, Voronoi jaotuseks ja ka Dirichlet' mosaiigiks (Peter Gustav Lejeune Dirichlet järgi). Voronoi diagramme kasutatakse paljudes valdkondades, enamasti teaduses ja tehnoloogias, kuid ka kujutavas kunstis.^[1][2]

Lihtsustatult võib Voronoi diagrammi vaadelda olukorrana, kus on antud lõplik arv punkte eukleidilisel pinnal. Sellisel juhul on iga ${\displaystyle \scriptstyle P_{k}}$ lihtsalt punkt ning sellele vastav Voronoi rakk (ka Voronoi rakk või Dirichlet'i rakk) ${\displaystyle \scriptstyle R_{k}}$ sisaldab kõiki punkte, mille vahemaa on vähem kui või võrdne iga teise ${\displaystyle \scriptstyle P_{k}}$ -ga. Iga selline rakk on saadud poolsfääride lõikumise teel ning on kumera hulknurga kujuga. Voronoi sõlmedeks on punktid, mis on võrdsel kaugusel kolmest või enamast algpunktist.

Ametlik määratlus

Olgu ${\displaystyle \scriptstyle X}$ meetriline ruum funktsiooniga ${\displaystyle \scriptstyle d}$. ${\displaystyle \scriptstyle K}$ on indeksite hulk ning ${\displaystyle \scriptstyle (P_{k})_{k\in K}}$ on lõplik jada mittetühjadest alamhulkadest ruumis ${\displaystyle \scriptstyle X}$. Voronoi rakk või Voronoi piirkond ${\displaystyle \scriptstyle R_{k}}$, mida seostatakse punktiga ${\displaystyle \scriptstyle P_{k}}$, on ${\displaystyle \scriptstyle X}$ kõikide punktide hulk, mille kaugus ${\displaystyle \scriptstyle P_{k}}$-ni ei ole suurem kui nende kaugus teiste algpunktideni ${\displaystyle \scriptstyle P_{j}}$, kus ${\displaystyle \scriptstyle j}$ on ${\displaystyle \scriptstyle k}$-st erinev indeks. Teisisõnu, kui ${\displaystyle \scriptstyle d(x,\,A)\;=\;\inf\{d(x,\,a)\mid a\,\in \,A\}}$ tähistab kaugust ${\displaystyle \scriptstyle x}$ ja alamhulga ${\displaystyle \scriptstyle A}$ vahel, siis

${\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{kõikide}}\;j\neq k\ {\text{jaoks}}\}}$

Voronoi diagramm on lõplik jada rakkudest ${\displaystyle \scriptstyle (R_{k})_{k\in K}}$. Printsipiaalselt võivad mõned algpunktid lõikuda ja isegi ühtida, aga enamasti eeldatakse, et need on siiski ühisosata. Lisaks on definitsiooni järgi lubatud lõpmatu palju algpunkte, aga tihti vaadeldakse ainult lõplikku arvu algpunkte. Erijuhul, kus ruumiks on lõplik dimensionaalne eukleidiline ruum, on ka lõplik arv punkte ning Voronoi rakud on kumerad polütoobid ning neid saab esitada, kombineerides tippe, külgi, 2-dimensionaalseid pindasid. Mõnikord nimetatakse indutseeritud ja kombineeritud struktuuri Voronoi diagrammiks. Üldiselt ei pruugi Voronoi rakud olla kumerad või isegi ühendatud. Tavalises eukleidilises ruumis saab uuesti kirjutada formaalse definitsiooni arusaadavamalt. Iga Voronoi polügoon ${\displaystyle \scriptstyle R_{k}}$ on seotud oma generaatori punktiga ${\displaystyle \scriptstyle P_{k}}$. Olgu ${\displaystyle \scriptstyle X}$ punktide hulk eukleidilises ruumis. ${\displaystyle \scriptstyle P_{1}}$ olgu punkt, mis genereerib selle Voronoi piirkonna ${\displaystyle \scriptstyle R_{1}}$, ${\displaystyle \scriptstyle P_{2}}$ genereerib ${\displaystyle \scriptstyle R_{2}}$ jne. Sel juhul on kõik asukohad Voronoi polügoonil lähemal generaatori punktile kui ükski teine generaatori punkt Voronoi diagrammil, mis asub eukleidilisel tasandil.^[3]

Illustratsioon

Voronoi diagrammi kirjeldamiseks sobib näide kaupluste hulgast linnas. Seda saab kasutada, kui tahetakse hinnata klientide arvu mingis poes, eeldusel, et kõik tingimused on võrdsed (tooted, hind, kvaliteet jne). Samuti on loogiline eeldus, et kliendid valivad külastatava poe kauguse järgi. Külastatakse lähimat kauplust. Sellisel juhul antud poe ${\displaystyle \scriptstyle P_{k}}$ Voronoi rakk ${\displaystyle \scriptstyle R_{k}}$ annab hinnangu potentsiaalse külastajate arvu kohta valitud kaupluses. Enamikus linnades on võimalik kaugust leida kasutades tuttavat eukleidilise kauguse leidmise valemit: ${\displaystyle \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}}}}$

või Manhattani kauguse valemit:

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

Omadused

• Voronoi diagrammi duaalne graafik vastab sama punktihulga Delaunay triangulatsioonile.
• Lähimad punktipaarid vastavad kahele naaberrakule Voronoi diagrammil.
• Omajagu üldiste tingimuste (lõpmatu dimensionaalne ühtlaselt kumer ruum, lõpmatult palju algpunkte üldises formuleeringus) juures omab Voronoi rakk stabiilsusomadust: algpunktide väike muutus kajastub Voronoi rakkude muutuses. See näitab Voronoi diagrammi geomeetrilist stabiilsust.^[4] Paraku ei leia see omadus üldiselt kinnitust, isegi kui ruum on kahedimensionaalne (aga mitteühtlaselt kumer ning eelkõige mitteeukleidiline).

Ajalugu

Voronoi diagrammide mitteametlik kasutus ulatub tagasi kuni Descartesini aastasse 1644. Dirichlet kasutas kahe- ja kolmemõõtmelisi Voronoi diagramme homogeensete teise astmega polünoomide uurimisel. Briti füüsik John Snow kasutas Voronoi diagrammi 1854. aastal illustreerimaks, kuidas enamik Soho koolera epideemiasse surnud inimestest elasid Broad Streeti pumbale lähemal kui mistahes teisele veepumbale. Voronoi diagrammid on saanud nime Vene-Ukraina matemaatiku Georgi Voronoi järgi, kes aastal 1908 defineeris ja uuris üldist n-mõõtmelist juhtu. Geofüüsikas ja meteoroloogias ruumiliselt jaotunud andmete (nagu näiteks sademete hulk) analüüsimiseks kasutatavaid Voronoi diagramme nimetatakse Ameerika meteoroloogi Alfred H. Thiesseni järgi Thiesseni hulknurkadeks. Tahkisefüüsikas teatakse taolisi mosaiike Wigner-Seitzi ühikrakkudena. Üldiste võrede jaoks Lie grupis, kutsutakse rakke fundamentaalseteks domeenideks. Üldistes meetrilistes ruumides kutsutakse neid rakke fundamentaalseteks polügoonideks.

Näited

• 2D-võre annab ebakorrapärase meekärje mosaiigi võrdsete kuusnurkadega koos punktisümmeetriaga. Tavalise kolmnurkse võre korral on see korrapärane, nelinurkse võre korral lähevad kuusnurgad üle nelinurkadeks ridades ja veergudes ning ruutvõre annab korrapärase ruutmosaiigi. Sealjuures peab meeles pidama, et nelinurgad ja ruudud on võimalik tulemusena saada ka teistest võredest (näiteks vektoritest (1,0) ja (1/2,1/2) saab ruudud).
• Lihtne kuupvõre annab kuubikujulise rakkude paiknemise.
• Paralleelsed pinnad korrapärase kolmnurkse võrega, mis on joondunud mõlema keskpunkti järgi, moodustavad heksagonaalse prismalise rakustruktuuri.

Üldistused ja variatsioonid

Nagu võib definitsioonist eeldada, saab Voronoi rakke defineerida ka eukleidilisest erinevates meetrikatest (nagu Mahalanobis või Manhattan). Ometi võivad neil juhtudel olla Voronoi rakkude piirid keerulisemad kui eukleidilise juhtumi puhul. Kaalutud Voronoi diagrammi puhul arvestatakse Voronoi raku defineerimisel ka asjaoludest tingitud lisakaaludega, arvestades neid generaatori punktide juurde. Sel juhul võivad mõned Voronoi rakud olla tühjad. Voronoi diagramm n punktiga ja d dimensiooniga nõuab ${\displaystyle \scriptstyle O\left(n^{\left\lceil {\frac {1}{2}}d\right\rceil }\right)}$ paigutusruumi. Seetõttu ei ole Voronoi diagrammid reaalselt teostatavad kui d > 2. Alternatiiviks on võimalus kasutada ligikaudseid Voronoi diagramme, kus Voronoi rakkudel ei ole selgeid piire, kuid mida saab eeldada.^[5] Teine alternatiiv on kasutada Voronoi diagrammi tegemisel ebaselgeid algpunkte, mis annaks ka ebaselged Voronoi rakud.

Kasutusalad

• Astrofüüsikas kasutatakse Voronoi diagramme, et genereerida piltidel adaptiivseid tasandustsoone. Peamiseks eesmärgiks on säilitada konstantne signaali-müra suhe kogu pildi ulatuses.
• Geomeetrias kasutatakse Voronoi diagramme leidmaks suurimat tühja ruumi keset antud punkte. Näiteks, kuhu ehitada supermarket, et see oleks teistest võimalikult kaugel.
• Hüdroloogias kasutatakse Voronoi diagramme, et kalkuleerida sademete hulka mingil maa-alal. Sellisel juhul teatakse neid Thiesseni polügoonidena.
• Arvutikeemias kasutatakse sellised Voronoi rakke, mis on defineeritud tuumade asukohtadena molekulis, aatomi laengute arvutamiseks.
• Materjaliteaduses esitatakse polükristallilisi mikrostruktuure metalli sulamites, kasutades Voronoi mosaiike. Tahkisefüüsikas teatakse Wigner-Seitzi rakku kui Voronoi rakku tahkisest.
• Kaevandamises kasutatakse Voronoi polügoone ennustamaks väärismaterjalide, -mineraalide vms reserve. Uurimuslikke puurauke kasutatakse kui algpunkte.
• Masinõppes kasutatakse Voronoi diagramme, et teha 1-NN klassifikatsioone.
• Bioloogias on Voronoi diagrammid kasutusel, et modelleerida erinevaid bioloogilisi struktuure, sealjuures ka rakke ^[6] ja luude mikrostruktuure.^[7]

Viited

1. Franz Aurenhammer (1991). Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 1991. Vaadatud 7. november 2015.
2. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Spatial Tessellations – Concepts and Applications of Voronoi Diagrams. 2nd edition. John Wiley, 2000, ISBN 0-471-98635-6. Vaadatud 8. november 2015.
3. Q.T.Tran, D.Tainar and M.Safar (2009) "Transactions on Large-Scale Data- and Knowledge-Centered Systems", lk 357. ISBN 9783642037214. Vaadatud 7. november 2015.
4. Daniel Reem, The geometric stability of Voronoi diagrams with respect to small changes of the sites, Full version: arXiv 1103.4125 (2011), Extended abstract in Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG 2011), lk 254–263. Vaadatud 8. november 2015.
5. S. Arya, T. Malamatos, and D. M. Mount, Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), lk 721–730. Vaadatud 8. november 2015.
6. Martin Bock (2009). "Generalized Voronoi Tessellation as a Model of Two-dimensional Cell Tissue Dynamics". Vaadatud 8. november 2015.
7. Hui Li (2012). "Spatial Modeling of Bone Microarchitecture". Vaadatud 8. november 2015.