Voronoi diagramm

Allikas: Vikipeedia

Voronoi diagramm on matemaatikas kasutusel olev mõiste, mis tähendab pinna jagamist osadeks seal asuvate punktide omavahelise kauguse arvestamise kaudu. Need algpunktid on varem defineeritud ning igale punktile kuulub vastav piirkond, mis moodustub kõige lähemal asuvatest punktidest. Iga punkti antud piirkonda nimetatakse Voronoi rakuks. Mingisuguse hulga punktide Voronoi diagramm on duaalne selle hulga Delaunay triangulatsiooniga. Lihtsalt öeldes 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 allik-punktidest.

Eukleidiline Voronoi diagramm

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

Lihtsuse ja arusaadavuse mõttes võib Voronoi diagrammi vaadelda olukorrana, kus on antud lõplik arv punkte eukleidilisel pinnal. Sellisel juhul on iga lihtsalt punkt ning sellele vastav Voronoi rakk (ka Voronoi rakk või Dirichlet'i rakk) sisaldab kõiki punkte, mille vahemaa on vähem kui või võrdne iga teise –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[muuda | muuda lähteteksti]

Olgu meetriline ruum funktsiooniga . on indeksite hulk ning on lõplik jada mittetühjadest alamhulkadest ruumis . Voronoi rakk või Voronoi piirkond , mida seostatakse punktiga , on kõikide punktide hulk, mille kaugus -ni ei ole suurem kui nende kaugus teiste algpunktideni , kus on -st erinev indeks. Teisisõnu, kui tähistab kaugust ja alamhulga vahel, siis

Voronoi diagramm on lõplik jada rakkudest . 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 on seotud oma generatoori punktiga . Olgu punktide hulk eukleidilises ruumis. olgu punkt, mis genereerib selle Voronoi piirkonna , genereerib 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[muuda | muuda lähteteksti]

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 Voronoi rakk annab hinnangu potentsiaalse külastajate arvu kohta valitud kaupluses. Enamikus linnades on võimalik kaugust leida kasutades tuttavat eukleidilise kauguse leidmise valemit:

või Manhattani kauguse valemit:

Omadused[muuda | muuda lähteteksti]

  • 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[muuda | muuda lähteteksti]

Voronoi diagrammide mitteametlik kasutus ulatub tagasi kuni Descartes’ini aastasse 1644. Dirichlet kasutas 2-dimensionaalseid ja 3-dimensionaalseid Voronoi diagramme seoses oma homogeensete teise astmega polünoomide uurimisega. Briti füüsik John Snow kasutas Voronoi diagrammi 1854. aastal illustreerimaks, kuidas enamik inimestest, kes surid Soho koolera epideemiasse, elasid lähemal Broad Street’i pumbale kui mistahes teisele veepumbale. Voronoi diagrammid on saanud nime Vene-Ukraina matemaatiku Georgi Voronoi järgi, kes defineeris ja uuris üldist n-dimensionaalset juhtu 1908. aastal. Voronoi diagramme, mida kasutatakse geofüüsikas ja meteoroloogias, analüüsimaks ruumiliselt jaotunud andmeid (nagu näiteks sademete hulk), nimetatakse Ameerika meteorologi Alfred H. Thiesseni järgi Thiesseni hulknurkadeks. Tahkisefüüsikas teatakse taolisi mosaiike Wigner-Seitzi ühikrakkudena. Üldiste võrede jaoks Lie grupis, kutsutakse rakke lihtsalt fundamentaalseteks domeenideks. Üldistes meetrilistes ruumides kutsutakse neid rakkusid fundamentaalseteks polügoonideks.

Näited[muuda | muuda lähteteksti]

  • 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[muuda | muuda lähteteksti]

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 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[muuda | muuda lähteteksti]

  • 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[muuda | muuda lähteteksti]

  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.