Matematicke modelovanı
VORONEHO DIAGRAMY
Oldrich Petrık
Osobnı cıslo: A07065Obor: Pocıtacova grafika a vypocetnı systemy
e-mail: [email protected]
Datum odevzdanı: 7.3.2008
Obsah
1 Uvod 5
2 Historie 5
2.1 Georgij Feodosjevic Voronoj . . . . . . . . . . . . . . . . . . . . 5
2.2 Historie Voroneho diagramu . . . . . . . . . . . . . . . . . . . . 6
3 Definice (obecny n-rozmerny prıpad) 7
4 Konstrukce 7
5 Jak vypadajı Voroneho diagramy 9
6 Prıklady problemu 11
6.1 Problem nejblizsı posty . . . . . . . . . . . . . . . . . . . . . . . 11
6.2 Problem skladky odpadu . . . . . . . . . . . . . . . . . . . . . . 12
7 Delaunayova triangulace 13
8 Zobecnenı 14
8.1 Pridanı vah . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.2 Rozsırenı generujıcı mnoziny . . . . . . . . . . . . . . . . . . . . 15
8.3 Pohyb bodu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
8.4 Zmena metriky . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
9 Pouzitı 16
9.1 Pocıtacova grafika . . . . . . . . . . . . . . . . . . . . . . . . . . 16
9.2 Biologie, prıroda . . . . . . . . . . . . . . . . . . . . . . . . . . 17
9.3 Chemie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
9.4 Geografie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
9.5 Geometricke problemy . . . . . . . . . . . . . . . . . . . . . . . 20
9.6 Robotika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
10 Shrnutı 20
1 Uvod
V teto praci se budu zabyvat problematikou delenı prostoru v zavislosti na
zadane mnozine bodu, konkretne zpusobem nazyvanym obvykle Voroneho dia-
gramy. Uvedu nekolik faktu z historie, definici zakladnıho principu teto metody
delenı prostoru, moznosti jejıho zobecnenı a nekolik algoritmu pouzıvanych
ke konstrukci Voroneho diagramu. Na zaver priblızım oblasti, ve kterych se
metoda v praxi pouzıva.
2 Historie
2.1 Georgij Feodosjevic Voronoj
Narodil se 28. dubna 1868 ve Zhuravce na Ukrajine. Jiz na gymnaziu projevoval
matematicky talent, zejmena v algebre. Vyresil problem spojeny s faktorizacı
polynomu, coz vedlo k jeho prvnı publikaci, clanku v casopisu Journal of Ele-
mentary Mathematics.
Po gymnaziu nastoupil ke studiu na Fakulte fyziky a matematiky Univerzity
v Petrohrade, kde se opet venoval predevsım algebre. Kdyz jeho otec odesel
do duchodu, musel Voronoj zacıt doucovat matematiku, aby pokryl naklady
na studia. To ho velmi vycerpavalo, presto v roce 1889 skolu uspesne dokoncil
disertacı o Bernoulliho cıslech. Rozhodl se ve studiu dale pokracovat a v roce
1894 ho zavrsil pracı na tema algebraickych cısel spojenych s koreny nero-
zlozitelnych kubickych rovnic.
V dalsıch letech vyucoval na Varsavske univerzite, kde zıskal titul profesora
matematiky. Obhajil doktorskou praci o retezovych zlomcıch, ktera byla na
tak vysoke urovni, ze za ni Voronoj zıskal Bunakovskeho cenu od Petrohradske
akademie ved. Jeho studenty na Varsavske univerzite byli mimo jine Boris De-
launay a Wac law Sierpinski. V roce 1895 se mu narodil syn Jurij Jurijevic, ktery
se stal prukopnıkem v transplantacnı medicıne a provedl prvnı transplantaci
ledvin.
Pozdeji se Voronoj zabyval hloubeji teoriı algebraickych cısel a take geometriı
cısel. Tehdy take zobecnil metodu delenı prostoru dnes nazyvanou Voroneho di-
agram. Roku 1907 se stal clenem Petrohradske akademie ved. Zacal se venovat
teorii indefinitnıch kvadratickych forem. V te dobe mel ale jiz velke bolesti
zpusobene zlucovymi kameny a praci na toto tema bohuzel nestihl dokoncit.
Zemrel 20. listopadu 1908 ve Varsave.
5
2.2 Historie Voroneho diagramu
Nekdy se take vyskytuje termın Voroneho teselace nebo delenı, zejmena v pro-
storech s dimenzı vyssı nez 2. Poprve se s neformalnım uzitım tohoto delenı
prostoru setkavame v Descartove praci ,,Principy filozofie“ z roku 1644, kde
s jejich pomocı ukazoval usporadanı hmoty ve slunecnı soustave a jejım okolı.
Dale dvou- a trırozmerne prıpady uzıval nemecky matematik Johann Peter
Gustav Lejeune Dirichlet ve sve studii o kvadratickych formach z roku 1850.
Podle nej se take pro diagram pouzıva nekdy termın Dirichletova mozaika a
pro bunku diagramu Dirichletova domena. Britsky fyzik John Snow v roce 1854
pomocı Voroneho diagramu vysvetlil rozsırenı cholery v londynske ctvrti Soho
v oblasti, ktera mela blıze k nakazene studne na Broad Street nez k ostatnım
studnam v okolı.
Diagram je pojmenovan po Georgiji Feodosjevici Voronem, ktery v roce 1908
definoval a studoval zobecnenou n-rozmernou formu tohoto delenı prostoru.
Voroneho diagramy se v geofyzice a meteorologii nekdy nazyvajı Thiessenovy
polygony podle americkeho meteorologa Alfreda H. Thiessena, pouzıvajı se zde
k analyze prostorove rozlozenych dat (merenı srazek, vlhkosti, atd.). Ve fyzice
materialu jsou zname take jako Wigner-Seitzovy jednotkove bunky. Diagramy
rustu krystalu s reciprokou mrızkou jsou nazyvany Brillouinovymi zonami,
na obecnych krystalovych mrızkach v Lieovych grupach se pak oznacujı jako
fundamentalnı domeny. V prostorech s obecnou metrikou se temto diagramum
rıka metricke fundamentalnı polygony.
V matematice jsou Voroneho diagramy specialnım prıpadem dekompozice met-
rickeho prostoru urcene vzdalenostmi od specificke diskretnı mnoziny objektu
v prostoru, naprıklad diskretnı mnoziny bodu. Krome matematiky se dnes
hojne pouzıvajı v biologii, medicıne, robotice, chemii, geografii, kartografii
apod.
6
3 Definice (obecny n-rozmerny prıpad)
Necht’ En je n-rozmerny euklidovsky prostor a S konecna nespojita mnozina
m bodu na tomto prostoru. Pro kazde dva body P,Q ∈ S;P 6= Q definujeme
delıcı nadrovinu ρ(P,Q) ≡ ρ(Q,P ) a dva poloprostory D(P,Q), D(Q,P ):
∀X ∈ ρ(P,Q); |P X| = |Q X|∀X ∈ D(P,Q); |P X| < |Q X|∀X ∈ D(Q,P ); |P X| > |Q X|
kde |P X| a |Q X| je vzdalenost bodu P resp. Q od bodu X. Potom Voroneho
bunka (prıpadne Voroneho oblast) ν(P, S) bodu P z mnoziny S je definovana
prunikem:
ν(P, S) =⋂
Q∈S\PD(P,Q)
a Voroneho diagram V or(S) definujeme jako sjednocenı hranic vsech takovych
bunek na mnozine S. Protoze bunky jsou otevrene mnozny, muzeme psat:
V (S) = En\( ⋃
P∈S
ν(P, S)
)
Z definice je zrejme, ze Voroneho diagram delı prostor En na m bunek. Kazda
pak obsahuje vsechny body, ktere majı nejblıze k jednomu bodu z mnoziny S.
Vsechny Voroneho bunky jsou konvexnı mnohouhelnıky. Nektere z nich jsou
nekonecne - ty korespondujı s body konvexnıho obalu (konvexnı obal mnoziny
bodu S v realnem vektorovem prostoru V je nejmensı mnozina obsahujıcı
S). Hranicı mezi dvema sousednımi oblastmi je usecka (prıpadne poloprımka
nebo prımka), ktera lezı na ose usecky spojujıcı odpovıdajıcı body sousednıch
oblastı. Obvykle se potkavajı tri Voroneho oblasti v jednom bodu, ktery se
nazyva Voroneho bod. Body definujıcı bunky, ktere se v tomto bode setkavajı,
lezı na jedne kruznici, jejız stredem je prave tento Voroneho bod.
4 Konstrukce
Pro vypocet Voroneho diagramu muzeme pouzıt nekolik algoritmu:
• Prunik polorovin
Prıma aplikace definice Voroneho diagramu — slozitost vypoctu jedne
bunky je O(n log n), tedy O(n2 log n) pro vypocet celeho diagramu.
• Inkrementalnı
Najdeme diagram pro nejaky jednoduchy prıpad (naprıklad vybereme
dva nebo tri body z mnoziny generatoru) a pak postupne pridavame po
jednom zbyle body.
7
• Rozdel a panuj
Zadanou generujıcı mnozinu rekurzivne rozdelujeme, dokud nemame mno-
zinu trı bodu, ze kterych jednoduse sestrojıme diagram. Pote zpetnym
chodem spojujeme diagramy castı v diagram celku. Algoritmus je na-
chylny na numericke chyby, ale vypocıta cely diagram v case O(n log n).
• Fortunova metoda (zametacı)
Pouzıva se tzv. zametacı prımka, kterou postupne pohybujeme jednım
smerem. Jak prımka prochazı body generujıcı mnoziny, z kazdeho bodu
konstruujeme parabolu — mnozinu bodu, ktere jsou stejne vzdalene od
generujıcıho bodu a zametacı prımky. S rostoucı vzdalenostı prımky a
bodu se parabola postupne rozevıra. Setkajı-li se dve paraboly, jejich
prusecık lezı na hrane Voroneho diagramu. V mıste, kde se setkajı tri
paraboly, vznika bod diagramu. Vypocıta cely diagram v case O(n log n).
• Metoda zdvihu
Transformacı prirazujeme bodu P = [px, py] paraboloid z = x2 + y2 a
rovinu z = 2pxx+ 2pyy − (p2x + p2
y), ktera je tecnou rovinou paraboloidu
v bode P = [px, py, p2x + p2
y] (P odpovıda kolmemu prumetu bodu P
na paraboloid). Najdeme vsechny obrazy bodu generujıcı mnoziny na
paraboloid odpovıdajıcı tecne roviny a projekce konvexnıho mnohostenu
vznikleho prunikem rovin je hledany Voroneho diagram.
• Z Delaunayovy triangulace
Mame-li k dispozici Delaunayovu triangulaci na zadane mnozine bodu,
muzeme na zaklade duality sestrojit Voroneho diagram. Najdeme stredy
opsanych kruznic vsech trojuhelnıku. Tyto jsou z principu duality Vo-
roneho body. Pro kazde dva sousedıcı trojuhelnıky spojıme stredy je-
jich opsanych kruznic, cımz zıskame hranice vnitrnıch Voroneho oblastı.
Hranice vnejsıch oblastı jsou pak poloprımky, ktere lezı na osach stran
konvexnıho obalu mnoziny generujıcıch bodu, viz Delaunayova triangu-
lace, 7.
• Pomocı kruznic
V kazdem bode z generujıcı mnoziny sestrojıme kruznici. Polomer vsech
kruznic pak nechame rust od nuly do nekonecna, pro vsechny body stejne.
Prusecıky dvou kruznic urcujı body na hranach diagramu, trı a vıce
kruznic pak vrcholy diagramu. Protnou-li se kruznice v nejakem bode,
jejich dalsı prusecıky s ostatnımi kruznicemi ve smeru od stredu kruznic
do tohoto bodu ignorujeme. V praktickych implementacıch na rastrovych
obrazech se rostoucı kruznice aproximujı pomocı dilatace.
8
5 Jak vypadajı Voroneho diagramy
Pokud je mnozina S dvoubodova (mame dana dve mısta P a Q), budou
oblastmi Voroneho diagramu poloroviny ohranicene osou usecky PQ.
D(P,Q) . . . otevrena polorovina obsahujıcı bod P
D(Q,P ) . . . otevrena polorovina obsahujıcı bod Q
Pro vıcebodovou mnozinu S je Voroneho oblast prunikem n − 1 polorovin a
proto jde o otevrenou konvexnı mnohouhelnıkovou oblast ohranicenou nejvyse
n− 1 vrcholy a nejvyse n− 1 hranami. Otevrene bunky nalezı bodum sıte Pi,
ktere tvorı konvexnı obal mnoziny S. Voroneho diagram je vzdy souvisly.
Obrazek 1: Konstrukce Voroneho diagramu
Hrany Voroneho diagramu jsou casti prımek — tedy usecky a poloprımky (na
okrajıch). Pokud jsou vsechny body sıte kolinearnı, jsou hrany dokonce cele
prımky, pokud existuje alespon jeden bod sıte nekolinearnı s ostatnımi, zadna
hrana pak nemuze byt prımkou (viz obr.2).
Obrazek 2: Voroneho diagramy pro sıt’ kolinearnıch bodu
Pomocı Eulerovy vety muzeme dokazat, ze pocet vrcholu diagramu V or(S) je
nejvyse 2n− 5 a pocet hran nejvyse 3n− 6, kde n je pocet bodu sıte mnoziny
S (Eulerova veta udava vztah mezi poctem vrcholu (V ), hran (E) a sten (F )
konvexnıho mnohostenu: V − E + F = 2).
9
Obrazek 3: Voroneho diagramy pro sıt’ obsahujıcı alespon ctyri body lezıcı nakruznici
Pridame nevlastnı vrchol (V + 1)− E + F = 2:∑i
di = 2E
V + 1 = 2 + E − n2E ≥ 3(V + 1) = 3(2 + E − n)
2E ≥ 3(2 + E − n)
3n− 6 ≥ E
E = (V + 1) + n− 2
2E = 2(V + 1) + 2n− 4
2(V + 1) + 2n− 4 ≥ 3(V + 1)
2n− 5 ≥ V
Dale vıme, ze hrany bunek jsou castmi os usecek PiPj, kde Pi, Pj jsou body
sıte mnoziny S a Voroneho vrcholy jsou prusecıky techto os. Vsechny osy ale
nemusı definovat hrany a vsechny prusecıky os nemusı tvorit vrcholy Voroneho
diagramu. Bod X lezı na hrane V or(S) prave tehdy, kdyz je stredem kruznice,
ktera prochazı dvema body sıte a zadny jiny bod sıte v teto kruznici nelezı.
Obdobne je vrcholem bod Y , ktery je stredem kruznice urcene (prochazejıcı)
tremi body sıte a zadny dalsı bod sıte uvnitr teto kruznice nelezı (viz obr.4).
10
Obrazek 4: Body na hranach a vrcholech Voroneho diagramu
Obrazek 5: Voroneho diagramy pro specialnı rozlozenı bodu sıte
6 Prıklady problemu
6.1 Problem nejblizsı posty
Ve meste se nachazı posty a je potreba zjistit, kterı obyvatele budou kazdou
z post navstevovat, tedy na kterou postu to majı nejblıze. Budeme predpokla-
dat nektera zjednodusenı (ktera muzeme zobecnovat - viz 8):
• Neuvazujeme prekazky v ceste - domy, zatacky, reky, atd., takze naklady
na cestu se rovnajı souctu ceny dopravy a ceny sluzeb (ty by mely byt
vsude stejne).
• Cenu dopravy zıskame jako soucin ceny za jednotku vzdalenosti (kon-
stantnı) a euklidovske vzdalenosti na postu.
Jindy budeme chtıt zjistit, do ktereho supermarketu chodı lide nakupovat.
V tom prıpade je treba minimalizovat celkove naklady, krome cesty tedy jeste
pribyva cena zbozı. V tomto modelu musıme pridat jeste dalsı zjednodusenı:
11
• Cena zbozı je stejna v kazdem obchode.
• Naklady na zıskanı zbozı jsou rovne souctu ceny zbozı a ceny dopravy.
• Zakaznık se snazı minimalizovat naklady na zıskanı zbozı.
• Faktory typu uroven sluzeb, sıre sortimentu atd. neuvazujeme.
Samozrejme zejmena predpoklady stejnych cen a linearnıho rustu ceny dopravy
uvnitr mesta nejsou idealnı, proto nam tento model poskytuje pouze hrubou
aproximaci problemu. Pri vymodelovanı situace se vytvorı takove oblasti, kde
lide bydlıcı v jedne z nich budou jezdit na postu (do obchodu) odpovıdajıcı
danemu regionu. To presne odpovıda definici Voroneho diagramu, kde posty
jsou body generujıcı sıte a regiony jsou Voroneho oblasti. Jakmile tedy ses-
trojıme Voroneho diagram, muzeme pomocı nej vyresit postovnı problem.
Obrazek 6: Postovnı problem a jeho Voroneho diagram
6.2 Problem skladky odpadu
Mame n bodu v rovine, ktere reprezentujı mesta, a potrebujeme najıt uloziste
toxickeho odpadu tak, aby se nachazelo co nejdal od mest. Zaroven je potreba
umıstit odpad dovnitr konvexnıho obalu bodu reprezentujıcıch mesta (za nım
uz je treba dalsı stat a odpad nenı mozne vyvazet). S touto podmınkou budou
vsechna potencialnı uloziste lezet ve Voroneho bodech diagramu generovaneho
sıtı mest a to skutecne nejvıc vzdalene najdeme v tom bode, ze ktereho je do
mest v sousednıch bunkach nejdale (viz Delaunyova triangulace, 7).
Stejnym postupem lze naprıklad resit problem umıstenı noveho obchodu. Chce-
me-li vybudovat novy obchod v urcene oblasti, bude nejvyhodnejsı ho umıstit
tak, aby byl co nejvıce vzdalen od vsech ostatnıch obchodu podobneho za-
merenı. Tım pokryjeme nejvetsı oblast zakaznıku, kterı budou mıt do naseho
obchodu blıze nez do ostatnıch. Protoze vlastne hledame kruznici s nejvetsım
polomerem se stredem v nekterem z Voroneho bodu, vsechny podobne prob-
lemy se souhrnne oznacujı problem nejvetsı kruznice.
12
7 Delaunayova triangulace
Delaunayovu triangulaci dostaneme, pokud spojıme navzajem useckami ty
body sıte, jejichz bunky ve Voroneho diagramu sousedı (viz obr.7). Delau-
nayova triangulace je dualnı k Voroneho diagramu, rozdeluje konvexnı obal
bodu na sıt’ trojuhelnıku a dıky dualite jedno urcuje druhe (tedy pokud mame
spocıtany Voroneho diagram, snadno dostaneme Delaunayovu triangulaci a
naopak). Takova triangulace lokalne maximalizuje nejmensı uhly. Uvnitr kruz-
nice opsane kazdemu jejımu trojuhelnıku nelezı zadny dalsı vrchol triangulace
(to vyplyva z konstrukce diagramu, viz 5). Protoze Voroneho diagram ma
nejvyse 3n−6 hran, v okamziku, kdy chceme najıt nejblizsı 2 body z generujıcı
sıte, stacı prohledat 3n−6 dvojic (ty, mezi nimiz existuje hrana v Delaunayove
triangulaci) namısto vsech n(n−1)2
dvojic puvodne pripadajıcıch v uvahu.
Nektere ze zajımavych vlastnostı Delaunayovy triangulace potom jsou:
• Dualita k Voroneho diagramu
Jedno urcuje druhe. Body prıslusne sousednım oblastem ve Voroneho
diagramu jsou spojeny hranou v Delaunayove triangulaci. Naopak spoj-
nice stredu opsanych kruznic dvou sousednıch trojuhelnıku v triangulaci
definuje hranu v diagramu. Hrana v triangulaci je kolma na hranici mezi
oblastmi v diagramu prıslusnymi ke koncovym bodum teto hrany.
• Vlastnost prazde kruznice
Kruznice opsana libovolnemu trojuhelnıku z Delaunayovy triangulace
neobsahuje zadny dalsı bod sıte.
• Jde o rovinny graf
Ma z Eulerovy vety maximalne 3n− 6 hran a 2n− 5 trojuhelnıku. Tato
vlastnost muze byt vyuzita pri redukci problemu z trıdy kvadraticke
slozitosti (nejblizsı par bodu) na linearnı. Samotna konstrukce triangu-
lace ma ale slozitost O(n log n)
• Obsahuje trojuhelnıky s maximalnım nejmensım uhlem
Snazı se tvar trojuhelnıku co nejvıce priblızit rovnostrannemu. Pokud
bychom sepsali seznam vsech uhlu v Delaunayove triangulaci ve vzes-
tupnem poradı a udelali totez s jakoukoliv jinou triangulacı stejne mno-
ziny bodu, delaunayovsky seznam bude urcite lexikograficky mensı.
13
Obrazek 7: Delaunayova triangulace a jejı maximalizace minimalnıho uhlu
8 Zobecnenı
Zobecnenım Voroneho diagramu rozumıme zmenu nekterych zakladnıch pred-
pokladu.
8.1 Pridanı vah
Jednotlivym bodum generujıcı sıte pridame vahy (to muze reprezentovat na-
prıklad nizsı ceny v nekterych obchodech z vyse uvedeneho problemu). Nynı
tedy mame mnozinu n bodu v rovine S = {P1, . . . , Pn} a k nim odpovıdajıcı
vahy v1, . . . , vn. Zmenıme definici oblasti: bod Q lezı v oblasti ν(Pi) prave
tehdy, kdyz
|QPi|vi
<|QPj|vj
∀j 6= i
Hranami tohoto Voroneho diagramu budou casti kruznic a casti prımek.
Obrazek 8: Pridanı vah bodum generujıcı sıte
14
8.2 Rozsırenı generujıcı mnoziny
Je mozne krome bodu pridat jako zdrojove objekty i prımky. Pak hledame
mnoziny bodu, ktere majı stejnou vzdalenost od pevne daneho bodu a prımky,
coz je definice paraboly, a mnoziny bodu se stejnymi vzdalenostmi od 2 bodu a
od 2 prımek (obojı jsou prımky). Hrany Voroneho diagramu takove generujıcı
mnoziny tedy budou casti prımek a casti parabol. Tyto diagramy se vyuzıvajı
naprıklad v GIS. Mnozinu S bychom mohli rozsırit jeste o oblouky krivek a
pak bychom museli zavest pojem osy krivky. Tato problematika by se resila
zavedenım axiomatickych a abstraktnıch Voroneho diagramu.
Stejne tak bychom mohli nadefinovat Voroneho diagram merenım vzdalenostı
k plocham mısto k bodum. Tyto typy Voroneho bunek se pouzıvajı v seg-
mentaci obrazu (to je potreba naprıklad pri jejich kompresi nebo dekompozici),
k optickemu rozpoznavanı charakteru a v dalsıch pocıtacovych aplikacıch. Ve
vyzkumu materialu jsou polykrystalizace mikrostruktur v kovovych slitinach
bezne reprezentovany pouzitım Voroneho mozaiky.
8.3 Pohyb bodu
Pro zacatek budeme uvazovat situaci, kdy v dane soustave generujıcıch bodu
P1, . . . , Pn−1, Pn budeme poslednım bodem Pn pohybovat. Zkoumanım topo-
logickych vlastnostı Voroneho diagramu bylo zjisteno, ze globalnı zmena nas-
tane tehdy, jestlize bod Pn pridavame nebo mazeme, nebo kdyz se zmenı kon-
vexnı obal mnoziny S = {P1, . . . , Pn−1, Pn}. V ostatnıch prıpadech se budou
menit pouze bunky prıslusne k sousednım bodum.
Slozitejsı prıpad nastane, nechame-li pohybovat vsechny body soustavy. Jako
analogii k problemu nejblizsı posty muzeme za generujıcı body sıte brat post’a-
ky, kterı se pohybujı po meste. Pohyb kazdeho z nich muzeme popsat rovnicı
pi = si +vit, kde si ∈ R je pozice i-teho post’aka v case t = 0 a vi jeho rychlost.
Mezi post’aky umıstıme dalsı pohybujıcı se osobu pi+1 a zajıma nas, ke komu
bude v case t = 0 nejblız a koho dohonı jako prvnıho. Resenı muze vest k dia-
gramu ve trıdimenzionalnım prostoru (x, y, t), kde osa t je kolma na zbyle dve
osy a znazornuje cas. V kazdem case tj mnozina bodu pi(tj) definuje rovinny
Voroneho diagram V or(pi(tj)). S pohybem generujıcıch bodu v case se menı
spojite odpovıdajıcı Voroneho diagram a vytvarı tak 3D objekty, kde hrany
diagramu generujı steny a vrcholy generujı hrany 3D diagramu (Voroneho di-
agram pohybujıcıch se bodu).
15
8.4 Zmena metriky
Voroneho diagramy nemusıme pocıtat pouze v euklidovske metrice, mohli
bychom pouzıt naprıklad metriku Lp, kde definujeme vzdalenost dvou bodu
v rovine P = [px, py], Q = [qx, qy] jako
||PQ||p = p
√|px − qx|p + |py − qy|p
||PQ||∞ = max {|px − qx| , |py − qy|}
Samozrejme v techto metrikach bude vypadat Voroneho diagram jinak nez
v Euklidovske metrice (viz obr.9).
Obrazek 9: Voroneho diagram v L1 metrice
9 Pouzitı
9.1 Pocıtacova grafika
V pocıtacove grafice se pomocı Voroneho diagramu vytvarejı barevne mozaiky.
V obrazku se vybere mnozina obrazovych bodu jako generujıcı mnozina dia-
gramu a kazda bunka se pak obarvı podle barvy prıslusneho bodu, cımz vznikne
efekt mozaiky. Tvar a velikost bunek lze ovlivnit vhodnou volbou rozmıstenı
a mnozstvım generujıcıch bodu. Tohoto postupu muzeme vyuzıt pri kompresi
digitalnıho obrazu, kdy se vytvorı mozaika a v kazde bunce se pak zabyvame
pouze rozdıly mezi barvou bunky a barvou zpracovavaneho bodu.
Jinou aplikacı je hledanı nejblizsıch sousedu v zadane mnozine bodu. Zkonstru-
ujeme-li nad mnozinou Voroneho diagram, stacı nam najıt nejkratsı vzdalenost
bodu prıslusnych sousednım bunkam. Tyto body jsou pak nejblizsı dvojicı.
Postup lze dale vyuzıt naprıklad k hledanı shluku v mnozine. Jestlize naprıklad
chceme rozlisit nekolik druhu objektu v obrazu, urcıme n klıcovych vlastnostı,
podle kterych je lze od sebe rozlisit. Vzorove objekty pak na zaklade techto
16
Obrazek 10: Dekompozice fotky na mozaiku pomocı Voroneho diagramu
vlastnostı umıstıme do n-rozmerneho prostoru a vytvorıme nad nimi Voroneho
diagram. Pro kazdy urcovany objekt pak stacı zjistit, do ktere bunky diagramu
patrı a tım se urcı jeho druh.
9.2 Biologie, prıroda
Biologicky model rustu rostlin — mame danou skupinu rostlin v rovine, ktere
jsou charakterizovane souradnicemi, polomerem a druhem. Ruzne druhy majı
rozdılna pravidla, podle kterych rostou a ktera definujı pomer mezi velikostı
oblasti, kterou rostlina okupuje, a sırkou teto rostliny. Nasım ukolem je stu-
dovat vztahy velikost–vzdalenost, velikost–plocha a vztahy v huste posazenem
systemu rostoucıch rostlin. K tomu se pouzıva vazeny euklidovsky Voroneho
diagram. Rostliny jsou reprezentovany body sıte, diagram je pro komunitu ros-
tlin konstruovan inkrementalnı metodou, oblast okupovana rostlinou se spocıta
jako obsah oblasti odpovıdajıcı bunky Voroneho diagramu.
Obdobne se da modelovat rust bunek v mitoze (zelena, obr.11) — ty obalujı
krevnı cesty (cervena) a jsou obalene odpocıvajıcımi bunkami (fialova), ktere
tvorı hrozny — skupiny bunek. Modre zobrazene rozlisene bunky doplnujı
prostor a obklopujı hrozny.
Vcelı plastve jsou take postavene do tvaru Voroneho diagramu, dokonce do
specialnıho mozaikoviteho prıpadu. Kazda larva ma mıt stejne velky a stejne
tvarovany prostor, cehoz se docılı prave tım, ze se specialne rozmıstene larvy
vezmou jako generujıcı body pro Voroneho diagram. Vysledna struktura bude
z hornıho pohledu mnozina sestiuhelnıku (obr.11).
Voroneho diagramy se take pouzıvajı k modelovanı teritoriı jednotlivych zvırat,
stad, tlup apod. Do bunek Voroneho bunek se tvarujı krıdla vazek. Morske
koraly si stavı bunky do tvaru Voroneho diagramu (kazdy tvorecek stavı roz-
dılnou rychlostı a v okamziku setkanı se sousedem uz nemuze pokracovat dal).
17
Obrazek 11: Model rustu rostlin (vlevo), simulace rustu bunek (uprostred),vcelı plastve
V dusledku smrst’ovanı a roztahovanı pudy kvuli zamrzanı a tanı tundry (Is-
land, severnı Evropa) nebo kvuli vysusovanı a zavodnovanı zeminy (solne
pouste v Jiznı Americe) do techto tvaru praska nebo se naopak shlukuje zem.
Dal je mozne v prırode pomocı 3D Voroneho diagramu modelovat srazky a
jejich regionalnı predpoved’.
Obrazek 12: Voroneho diagramy v prırode - krıdlo vazky, poust’ Atacama,tundra na Islandu, koral
9.3 Chemie
Voroneho mozaikovy rozklad — bezny 3D model bunek, chemickych prvku
apod. — se vykresluje jako Voroneho mozaika generujıcıch bodu v prostoru.
Kolem kazdeho bodu je oblast, jejız vsechny body jsou k bodu sıte blız nez ke
kteremukoliv dalsımu. Pri konstrukci 3D diagramu nechame z kazdeho bodu
sıte rust kouli, vsechny stejnou rychlostı. Tam, kde se dve sousednı dotknou,
dostavame kontaktnı bod. Po projitı vsech bodu muzeme sestrojit Voroneho
diagram, kde jsou vsechny oblasti konvexnımi mnohosteny. Polygony nalezıcı
bodum konvexnıho obalu jsou otevrene. Na obrazku 13 vlevo je aproximace
Kelvinovy peny Voroneho diagramem — vsechny bunky majı jednotny tvar,
jsou plne a splnujı Plateau pravidlo penove rovnovahy (tri steny se potkavajı
pod uhlem 120◦ a ctyri vzpery pod uhlem 109,5◦). Aby toto platilo, musı byt
steny a hrany lehce zahnute.
18
Pokud potrebujeme namodelovat tvar krystalu nejake latky, stacı nam znat
rozlozenı atomu v nem. Ty pak bereme jako generujıcı mnozinu bodu pro
Voroneho diagram, ten sestrojıme, najdeme Delaunayovu triangulaci a ta je
pak velmi dobrou aproximacı tvaru krystalu (obr.13 vpravo). Voroneho dia-
gramy se take pouzıvajı k urcenı strukturalnıch vlastnostı proteinu (nalezenı
nejvetsıho volneho prostoru, konstrukce povrchu molekul atd.).
Obrazek 13: 3D Voroneho diagramy vyuzıvane v chemii
9.4 Geografie
V geografii se Voroneho diagramy vyuzıvajı k analyze sıdel. Naprıklad ro-
zlozıme Zemi na polygony zalozene na hustote lidske populace. Kde je vyssı
hustota obyvatel, bude vıc bunek (a samozrejme budou mensı). Tam, kde zije
obyvatel malo, vznikne malo velkych regionu — viz nasledujıcı obrazek.
Obrazek 14: Regiony s konstantnım poctem obyvatel
19
9.5 Geometricke problemy
Pomocı Voroneho diagramu se resı take velke mnozstvı geometrickych prob-
lemu. Jak usporadat kabely ruzneho prumeru do valcoveho objektu, problem
nalezenı nejkratsı cesty, stromu s nejkratsım souctem delek hran (MST, mi-
nimal spanning tree), problem nejvetsıho toku nebo vyse zmınene problemy
nejvetsı kruznice a nejblizsı posty. Nalezenım MST pak muzeme aproximo-
vat resenı problemu obchodnıho cestujıcıho. Nalezena cesta bude v nejhorsım
prıpade dvakrat delsı nez optimalnı resenı, ovsem vymenou za znacne urychlenı
vypoctu.
9.6 Robotika
V kybernetice a robotice se Voroneho diagramy pouzıvajı pro planovanı cesty
robotu a jinych pohybujıcıch se stroju. Vyuzijeme zobecneneho Voroneho dia-
gramu, kdy generujıcı mnozinou budou prekazky v prostoru. Nad nimi potom
zkonstruujeme diagram. Bude-li se robot pohybovat po hranach diagramu,
bude v kazdem okamziku v idealnı pozici vzhledem k prekazkam, nebot’ od
tech nejblizsıch bude mıt stejnou vzdalenost.
10 Shrnutı
Delenı prostoru zname jako Voroneho diagram se poprve objevilo jiz v sedm-
nactem stoletı. Jeho vetsı vyuzitı je zdokumentovano ve stoletı devatenactem.
Pocatkem dvacateho stoletı se diagramy zabyval nadany rusky matematik
G. F. Voronoj, ktery provedl jejich zobecnenı a po nem byly take pojmenovany.
Voroneho diagramy jsou delenım prostoru na zaklade generujıcı mnoziny bodu,
kdy v kazde bunce je euklidovska vzdalenost vsech bodu od prıslusneho generu-
jıcıho bodu mensı nez vzdalenost od vsech ostatnıch bodu generujıcı mnoziny.
Definici je pak mozne v ruznych smerech zobecnovat, naprıklad pouzitım jinych
geometrickych utvaru jako generujıcı mnoziny, pouzitım jine metriky ci prida-
nım vah k bodum.
Uplatnenı nachazı Voroneho diagramy v mnoha odvetvıch. Jejich vyskyt lze
dohledat v ruznych prırodnıch jevech, od teritoriı zvırat pres bunecne struktury
az po rust krystalu. Z toho se take odvıjı jejich vyuzitı ve vedach studujıcıch
takove jevy — biologii, chemii, ale treba i geologii. Lze je pouzıt k modelovanı
vlivu sıdel, kultur, jazyku a podobne. Velkeho vyuzitı nachazı v pocıtacove
grafice a vypocetnı geometrii, kde se pomocı nich resı mnoho problemu. V ne-
poslednı rade jsou pak Voroneho diagramy vyuzıvany naprıklad v kybernetice
k rızenı pohybu stroju.
20
Reference
[bas] Bohumır Bastl: Aplikace geometrie 2 - pomocny ucebnı text
[jez] Frantisek Jezek: Aplikace geometrickeho modelovanı (24. konference o
geometrii a pocıtacove grafice)
[kap] Craig S. Kaplan: Voronoi diagrams and ornamental design
[sug] Kokichi Sugihara: Voronoi Diagrams
[tom] Svetlana Tomiczkova: Voroneho diagramy
[bio] http://www-history.mcs.st-andrews.ac.uk/Biographies/Voronoy.html
[can] http://www-imagis.imag.fr/Membres/Marie-Paule.Cani/Lave/
[csk] http://www.cgl.uwaterloo.ca/∼csk/projects/voronoi/
[epp] http://www.ics.uci.edu/∼eppstein/gina/voronoi.html
[exp] http://www.experiencefestival.com/a/Voronoi diagram/id/1970321
[gar] http://ciks.cbt.nist.gov/∼garbocz/closedcell/node5.html
[geo] http://www.cs.unc.edu/∼geom/voronoi/
[hje] http://www.diku.dk/hjemmesider/studerende/duff/Fortune/
[sct] http://www.snibbe.com/scott/bf/index.htm
[wiki] http://www.wikipedia.org
21
