Voronoi diagramm

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 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 väga paljudes valdkondades, enamasti teaduses ja tehnoloogias, kuid ka kujutavas kunstis.

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
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 generaatori 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.

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  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
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. 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 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 Streeti 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 meteoroloogi 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
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  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. 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  ja luude mikrostruktuure.

Viited

Geomeetria