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.
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.
Lihtsustatult võib Voronoi diagrammi vaadelda olukorrana, kus on antud lõplik arv punkte eukleidilisel pinnal. Sellisel juhul on iga formula_1 lihtsalt punkt ning sellele vastav Voronoi rakk (ka Voronoi rakk või Dirichlet'i rakk) formula_2 sisaldab kõiki punkte, mille vahemaa on vähem kui või võrdne iga teise formula_1 -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 formula_4 meetriline ruum funktsiooniga formula_5. formula_6 on indeksite hulk ning formula_7 on lõplik jada mittetühjadest alamhulkadest ruumis formula_8. Voronoi rakk või Voronoi piirkond formula_2, mida seostatakse punktiga formula_1, on formula_4 kõikide punktide hulk, mille kaugus formula_1-ni ei ole suurem kui nende kaugus teiste algpunktideni formula_13, kus formula_14 on formula_15-st erinev indeks. Teisisõnu, kui formula_16 tähistab kaugust formula_17 ja alamhulga formula_18 vahel, siis
formula_19
Voronoi diagramm on lõplik jada rakkudest formula_20. 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 formula_2 on seotud oma generaatori punktiga formula_1. Olgu formula_8 punktide hulk eukleidilises ruumis. formula_24 olgu punkt, mis genereerib selle Voronoi piirkonna formula_25, formula_26 genereerib formula_27 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.
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 formula_1 Voronoi rakk formula_2 annab hinnangu potentsiaalse külastajate arvu kohta valitud kaupluses.
Enamikus linnades on võimalik kaugust leida kasutades tuttavat eukleidilise kauguse leidmise valemit: formula_30
või Manhattani kauguse valemit:
formula_31
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.
Ü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 formula_32 paigutusruumi. Seetõttu ei ole Voronoi diagrammid reaalselt teostatavad kui d &gt; 2. Alternatiiviks on võimalus kasutada ligikaudseid Voronoi diagramme, kus Voronoi rakkudel ei ole selgeid piire, kuid mida saab eeldada. Teine alternatiiv on kasutada Voronoi diagrammi tegemisel ebaselgeid algpunkte, mis annaks ka ebaselged Voronoi rakud.