3 \prednaska{9}{Geometrické algoritmy}{(B. Maslowski, J. Návrat, M. Sta¹a)}
5 \>Budeme se teï bavit o geometrických problémech v~rovinì. Vìt¹ina algoritmù,
6 které zde uvedeme, má sice své obdoby i pro prostory vy¹¹í nebo ni¾¹í dimenze,
7 ale jednorozmìrné pøípady bývají triviální a vícerozmìrné jsou zase vìt¹inou
10 Budeme se tedy zabývat tím, jak tyto problémy øe¹it v~dimenzi dva
11 (v~Euklidovské rovinì).
13 \h{Hledání konvexního obalu}
15 Ptáte se o co pùjde? Zkusme si to pøiblí¾it na problému ledních medvìdù :) {\I
16 Lední medvìdi si po dlouhé dobì zmapovali vody severního moøe a zjistili
17 pøesnì místa, kde se nacházejí jejich oblíbené ryby. No a proto¾e to jsou
18 medvìdi chytøí, rozhodli se v¹echny tyto rybky pochytat najednou do jedné
19 velké sítì. A problém, který tady mají, je následující: jaký nejmen¹í obvod
20 mù¾e mít taková sí», aby se dovnitø ve¹ly v¹echny rybky?!}
22 Neboli budeme øe¹it, jak nìjakou zadanou mno¾inu bodù v~rovinì obalit co
23 nejkrat¹í uzavøenou køivkou, do které se je¹tì v¹echny body vejdou.
25 Intuice nám napovídá ¾e výsledek bude nìjaký konvexní\foot{Mno¾ina bodù
26 v~rovinì je konvexní, pokud platí, ¾e pro ka¾dé dva body této mno¾iny le¾í
27 úseèka spojující tyto dva body také celá v~této mno¾inì.} mnohoúhelník, který
28 bude mít vrcholy v~nìkterých uvedených bodech. Ostatní vrcholy pak budou buï
29 nìkde na hranách mnohoúhelníku, nebo uvnitø. Tomuto mnohoulehníku se øíká {\I
30 konvexní obal} dané mno¾iny.
32 \>Mo¾ná by se teï hodilo pøedvést názornì, jak vypadají nejmen¹í konvexní
35 \figure{ZakladniObaly.eps}{Základní obaly.}{3in}
39 \:Konvexní obal prázdné mno¾iny je prázdná mno¾ina.
41 \:Konvexní obal 1 bodu je bod samotný.
43 \:Konvexní obal 2 bodù je úseèka spojující tyto body.
45 \:Konvexní obal 3 bodù je trojúhleník s vrcholy v~tìchto bodech.
47 \:Konvexní obal 4 bodù \dots to u¾ je slo¾itìj¹í\dots
51 Konvexní obaly 4 a více bodù, jak si mù¾eme v¹imnout, u¾ nejsou jednoznaèné.
52 Pro $N$-prvkovou mno¾inu bude konvexní obal mnohoúhelník se tøemi a¾ $N$
55 Jeden dobrý zpùsob, jak tento konvexní obal sestrojit se nazývá {\I Zametání
58 Algoritmus funguje tak, ¾e si v~rovinì zvolíme nìjaký smìr, a v~tomto smìru
59 zaèneme posouvat pøímku. Budeme takto potkávat body le¾ící v~na¹í mno¾inì.
60 V~ka¾dém okam¾iku budeme chtít, aby body v~èásti, kterou jsme ji¾ zametli, u¾
61 mìli spoèítaný konvexní obal. V¾dy kdy¾ pak zametací pøímkou narazíme na nový
62 bod, u¾ si jen rozmyslíme, jak ho do konvexního obalu pøidat.
64 BÚNO pøedpokládáme body v~obecné poloze, tedy takové, ¾e ¾ádné tøi nele¾í
65 na~jedné pøímce. Dále také budeme pøedpokládat, ¾e budeme zametat ve smìru
66 $x$-ové osy a ¾e v¹echny body mají rùznou $x$-ovou souøadnici.
68 Je také vidìt, ¾e bod s nejmen¹í a nejvìt¹í $x$-ovou souøadnicí bude le¾et
71 \s{My¹lenka algoritmu:}
75 \:Setøídíme body podle jejich $x$-ové souøadnice.
77 \:Vezmeme první tøi body a sestrojíme jejich konvexní obal.
79 \:Opakuj: Najdeme dal¹í bod a podíváme se, jestli ho mù¾eme do konvexního
80 obalu rovnou pøidat: \::Pokud jej mù¾eme rovnou pøidat, tak jej pøidáme.
82 \::Pokud jej pøidat rovnou nemù¾eme, pak je potøeba nejdøíve nìjaké body
83 odzadu odebrat a pak teprve pøipojit ná¹ nový bod. \endalgo
85 Ka¾dá iterace tedy bude probíhat tak, ¾e nìjaké body z pùvodního konvexního
86 obalu pozapomínáme a pøidáme nový bod. Aby se to lépe popisovalo, tak celý
87 konvexní obal rozdìlíme na {\I horní obálku} a {\I dolní obálku.}
89 \figure{HD-obalka.eps}{Obrázek obálek.}{3in}
91 Vidíme teï, ¾e dolní obálka je nìjaká lomená èára, která zatáèí doleva. Horní
92 obálka zatáèí doprava. V~na¹em algoritmu si budeme obálky pamatovat jako dva
93 seznamy vrcholù. Kdy¾ pak v~algoritmu narazíme na nový bod, budeme zvlá¹»
94 øe¹it jak to ovlivní horní obálku a jak ovlivní dolní. Je vidìt ¾e bod nejvíce
95 vlevo a bod nejvíce vpravo le¾í v obou obálkách. Ostatní body buï le¾í jen
96 v~jedné z obálek, nebo nele¾í v~¾ádné z nich (tedy nejsou souèástí konvexního
103 \:Setøídíme body podle souøadnice $x$, dostaneme mno¾inu bodù $b_1~-~b_n$.
104 \:Spoèítáme konvexní obal ${b_1, b_2, b_3}$, z toho získáme horní a dolní
105 obálku\foot{Body $b_1$ a $b_3$ budou v obou obálkách. Bod $b_2$ bude v~horní
106 obálce pokud le¾í nad pøímkou spojující $b_1$ a $b_3$, v~dolní obálce bude
107 pokud le¾í pod pøímkou.}. \:Pro $b$ postupnì zpracováváme $b_3 - b_n$:
109 \::Pøepoèítáme Horní obálku:
111 \:::Dokud $(\vert H\vert \geq 2)$ a úhel $(H[-2], H[-1], b)$ je orientovaný
112 doleva: \::::Odebereme poslední prvek z obálky.
114 \:::Pøidáme do obálky nový vrchol.
116 \::Pøepoèítáme dolní obálku:
118 \:::Dokud $(\vert D\vert \geq 2)$ a úhel $(D[-2], D[-1], b)$ je orientovaný
119 doprava: \::::Odebereme poslední prvek z obálky.
121 \:::Pøidáme do obálky nový vrchol.
125 Setøídit body podle $x$-ové souøadnice a sestrojit konvexní obal prvních tøech
126 bodù stihneme v~èase $\O(n \log n)$. Zbytek pak u¾ udìláme dokonce v~èase
127 lineárním $\O(n)$\foot{V této èásti u¾ jen do obálek pøidáváme a odebíráme
128 body.Pøidáváme jich $N$. A odebrat jich mù¾eme maximálnì tolik kolik jsme jich
129 pøidali. Tedy zase maximálnì~$N$.}. Platí tedy:
131 \s{Vìta:} Konvexní obal doká¾eme sestrojit v~èase $\O(n \log n)$.
133 \>Na¹i lední medvìdi se tedy ji¾ nauèili, jak si efektivnì obstarat potravu a
134 mohly se pustit do øe¹ení dal¹ího velmi dùle¾itého problému. Pojïme se na nìj
135 podívat s nimi. \>A o co ¾e to pùjde?
137 {\I Lední medvìdi nejsou na antarktidì sami, kromì nich tam taky bydlí
138 kamarádi eskymáci ve svých iglù. Medvìdi by si teï rádi udìlali mapu, podle
139 které by hned poznali, ke kterému ekymákovi to mají nejblí¾e na náv¹»evu.}
141 My tuhle medvìdí mapu od teï budeme nazývat {\I Voroneho diagramem}.
143 \h{Voroného diagramy}
145 Pøed tím, ne¾ vás vystra¹ím nìjakou definicí, si øekneme, co jsi pod tímto, na
146 první pohled ne zøejmým pojmem, pøedstavit. Mìjme mno¾inu teèek $T$
147 rozmístìných náhodnì po papíru. Ke ka¾dému bodu nakreslíme okraje tak, aby
148 vniklá plo¹ka obsahovala body, které jsou nejblí¾e právì té na¹í vybrané
149 teèce. Samozøejmì \uv{sousední} teèky budou mít tyto hranice spoleèné.
150 Výsledkem na¹eho dlouhého sna¾ení pak bude právì Voroného diagram. V dal¹ích
151 odstavcích se budeme zajímat o to, jak takový útvar správnì popsat, jak ho
152 sestrojit a jaké datové struktury k tomu pou¾ít.
154 \s{Definice:} {\I Voroného diagram} pro koneènou mno¾inu $M = \{m_1, \dots,
155 m_n\} \in {\bb R}^2$ míst je systém mno¾in $O_1,\dots,O_n$ takových, ¾e pro
156 v¹echna $i$ a $j$ a pro v¹echna $x \in M_i$ je vzdálenost $x$ od $m_i$ men¹í
157 nebo rovna vzdálenosti $x$ od $m_j$ a zároveò sjednocení $O_i$ pøes v¹echna
158 $i$ je celý prostor ${\bb R}^2$, neboli:
160 $$d(x,m_i) \leq d(x,m_j) \wedge {\bigcup}_i O_i = {\bb R}^2.$$
162 Jednoduchý Voroného diagram:
164 \figure{voroneho2.eps}{Voroneho diagramu pro dvì místa.}{3in}
166 Voroného diagram se tedy skládá z nìjakých míst, oblastí a hran, které ty
169 \figure{voronoi.eps}{Èásti Voroneho diagramu.}{2in}
171 \s{Definice:} Øekneme, ¾e {\I hrana} $H$ je taková mno¾ina bodù, ¾e pro ka¾dý
172 bod $x \in H$ platí, ¾e existují dvì místa $m_i$ a $m_j$, od kterých má bod
173 $x$ stejnou vzdálenost. Tyto dvì místa jsou pro v¹echny body $x$ stejná a
174 platí, ¾e v¹echny ostatní místa mají od ka¾dého bodu $x$ del¹í vzdálenost.
176 \s{Definice:} Øekneme, ¾e {\I vrchol} je takový bod, kde se potkávají alespoò
183 \:Voroneho diagramem pro dvì místa jsou dvì poloroviny odìlené takovou pøímkou,
184 ¾e ka¾dý bod pøímky je stejnì vzdálený od obou míst. \:Ka¾dá mno¾ina $M_i$ je
185 ohranièena konvexní lomenou èarou, tak¾e oblasti mají tvar konvexních
186 mnohoúhelníkù, ale je mo¾né, ¾e jsou oteveøené do nekneèna. \:Pro ka¾dou hranu
187 $h$ ve Voroného diagramu existuje $i$ a $j$ takové, ¾e kdy¾ $x \in H$, pak
188 vzdálenost $d(x,m_i) = d(x,m_j)$. \:Pro ka¾dý vrchol $v$ Voroného diagramu
189 existují alespoò tøi místa le¾ící na kru¾nici se støedem $v$.
191 \figure{body.eps}{Body na kru¾nici.}{3in}
193 \:Poèet vrcholù a hran je lineární k poètu míst\foot{Voroneho diagram si lze
194 pøedstavit jako graf, kde místa Voroneho diagramu odpovídají stìnám, vrcholy
195 diagramu vrcholùm a hrany odpovídají hranám grafu. Pokud si teï nìkam mimo
196 graf pøidáme je¹tì jeden vrchol a v¹echny pøímky vedoucí do nekoneèna navedeme
197 do toho bodu, vidíme, ¾e ná¹ graf je roviný. Pro roviný graf platí Eulerova
198 formule a z ní u¾ plyne ¾e na¹e linearita.}. \:Poèet krajních oblastí je tak
199 velký, jak velký je konvexní obal té zadané mno¾iny. (Je to dobré vìdìt, ale
200 asi to nebudeme potøebovat.)
204 Pojïme teï vymyslet, jak takový diagram vyrobit. Mohli bychom zkonstruovat
205 v¹echny dìlící pøímky a poslepovat je, ale vznikl by nám kvadratický
206 algoritmus a to nám nemù¾e staèit.
208 Mluvili jsme o zametání roviny, a tak bychom tento trik mohli vyu¾ít právì pøi
209 øe¹ení na¹eho problému. Ov¹em tentokrát má zametání jeden podstatný háèek.
210 Kdy¾ si vezmeme nìjakou zametací pøímku a pojedeme s ní shora dolù, tak nad ní
211 máme nìjakou u¾ zkonstruovanou èást diagramu a kdy¾ narazíme na dal¹í bod, tak
212 se nám mù¾e právì tato èást diagramu pomìrnì slo¾itì zmìnit. Pomù¾eme si malým
213 trikem. Nebudeme pova¾ovat za hotovou celou oblast nad zametací pøímkou, ale
214 jen takové body, které mají blí¾e k místùm ($m_i$) ne¾ k zametací pøímce. Tak
215 dostaneme nìjakou posloupnost (mno¾inu) parabol. V¹echno, co jsme spoèítali
216 uvnitø této oblasti nám u¾ nikdo nepokazí (ani nevylep¹í), je tam bezpeèno.
217 Vezmeme si tedy dolní obálku tìchto parabol, budeme jí øíkat {\I pobøe¾í}.
219 \figure{pobrezi.eps}{Pobøe¾ní linie.}{3in}
221 Pobøe¾í je tedy nìjaká posloupnost parabolických obloukù s tím, ¾e nejlevìj¹í
222 a nejpravìj¹í jdou do nekoneèna. Prùseèíky tìchto obloukù vykreslují hrany
223 diagramu. Proè? Odpovìï na tuto otázku není tì¾ká, staèí vyjít z definice
224 paraboly tak, jak jí zde pou¾íváme. Nebo-li je to mno¾ina bodù, která je od
225 ohniska (pro nás místa) stejnì vzdálená jako od pøímky (øídící). A tedy prùnik
226 dvou parabol je místo, které je stejnì vzdálené od obou ohnisek, co¾ je
227 vlastnì definice bodu le¾ícího na nìjaké hranì.
229 Kdykoliv v prùbìhu zametání narazíme na nìjaký bod, mù¾e nám ovlivnit u¾ jen
230 èást diagramu pod pobøe¾ím. Dostáváme se tedy k tomu, co se dìje, kdy¾ hýbeme
231 zametací pøímkou. Pakli¾e nenará¾íme na ¾ádné body, tak se v podstatì nedìje
232 nic zajímavého. Zajímavá situace nastává a¾ tehdy, narazíme-li na dal¹í bod.
233 V~tom okam¾iku vzniká nová parabola. V tuto chvíli je znaènì degenerovaná. Je
234 to toti¾ zatím jen polopøímka kolmá na zametací pøímku. S dal¹ím pohybem se
235 zaène parabola rozevírat. V¹imnìme si, ¾e prùnik oné pøímky a pobøe¾í je
236 vlastnì vrchol Voroného diagramu.
238 Mù¾e nastat je¹tì jeden problém. Nìjaká parabola se mù¾e natolik rozevøít, ¾e
239 pohltí jiné a ty zmizí z pobøe¾ní linie. V takovém pøípadì, se nám ale
240 netriviálnì zmìní vzhled pobøe¾í, a proto se této situaci budeme muset více
243 Shrneme-li na¹e úvahy, mohou se dít celkem tøi vìci. Jedna z nich je posun
244 pøímky. To se vlastnì dìje poøád. Pobøe¾í se témìø nemìní a prùseèíky parabol
245 nám kreslí hrany. To mù¾eme poèítat najednou. Navíc nejen ¾e bychom mohli s
246 pøímkou skoèit o nìjaké epsilon, ale my dokonce mù¾eme skoèit o poøádný kus a
247 prostì pouze dopoèítat, jak se pobøe¾í zmìnilo a co se vykreslilo. Dùle¾itým
248 místùm, kde se budeme zastavovat, budeme øíkat {\I události}.
250 \>{\I Místní událost}
252 Pokud narazíme na bod, musíme najít místo, kde pobøe¾í rozetnou a kam vklínit
253 dal¹í výbì¾ek (parabolu). Takovéto události budeme øíkat místní událost.
255 \figure{mistni.eps}{\vbox{\hsize=0.6\hsize\leftskip=0pt plus
256 0.3\hsize\rightskip=\leftskip\parfillskip=0pt \>Místní událost -- èervená
257 kolmice je novì vznikající parabola, pøi postupu zametací pøímky dále se bude
258 rozevírat a vytvoøí dal¹í parabolu.}}{3in}
260 \>{\I Kru¾nicová událost}
262 Poslední situace, která mù¾e nastat, je, ¾e se nìjaká parabola schová za jiné.
263 Kouknìme se na první obrázek ní¾e, fialový bod je støed kru¾nice opsané
264 trojùhelníku tvoøenému tøemi místy. Jak víme, ten le¾í na osách stran takového
265 trojùhelníku. Po tìchto osách se v¹ak budou i pohybovat prùseèíky parabol a s
266 posunováním øídící pøímky se pak dostanou v¹echny tøi do støedu této kru¾nice.
267 Stane se to pravì tehdy, kdy¾ se zametací pøímka dotkne kru¾nice zespodu. Je
268 mo¾né nahlédnout, ¾e pøi postupu dále se pak dvì krajní paraboly roz¹íøí
269 natolik, ¾e prostøední pohltí a ta zanikne. Takto vzniklé události budeme
272 Pojïme si to ukázat lépe na následujících dvou obrázcích. První pøedstavuje
273 situaci pøed kru¾nicovou událostí a druhý právì kru¾nicovou událost. Mimo jiné
274 by tedy z obrázkù mìlo být patrné, ¾e kru¾nicové události jsou urèeny
275 trojicemi sousedních obloukù v pobøe¾í.
277 \figure{kruznicova.eps}{Pøed kru¾nicovou událostí.}{3in}
279 \figure{kruznicovakonec.eps}{Kru¾nicová událost.}{3in}
283 Budeme potøebovat haldu událostí (místních i kru¾nicových dohromady).
285 Dále bude zapotøebí udr¾ovat si pobøe¾ní linii, neboli posloupnost míst
286 v~ohniscích parabolických obloukù. Zde je potøeba si definovat operace {\I
287 Insert, Delete} a {\I FindX}, jinak øeèeno pøidat a odebrat oblouk a najít
288 oblouk podle x-sové souøadnice nebo-li oblouk do kterého jsme se trefili pøi
289 místní události. Navíc budeme potøebovat vyhledávací strom nad prùseèíky s
290 implicitní reprezentací, co¾ znamená, ¾e si ve vrcholech nebudeme pamatovat
291 pøímo souøadnice prùseèíkù, ale jen instrukci, jak je spoèítat. Tak¾e jakkoli
292 se mìní poloha prùseèíkù, tak struktura stromu zùstává stejná.
294 S haldou událostí lze pracovat s logaritmickou èasovou slo¾itostí na operaci
295 a ve stejném èase doká¾eme pracovat s pobøe¾ní linií. Kdy¾ si pobøe¾í je¹tì
296 reprezentujeme zvlá¹» jako seznam tak Insert a Delete budou v konstatním èase
297 a operace se stromem pak $\O(\log n)$.
299 Poslední datovou strukturou bude samotný diagram, reprezentovaný grafem se
300 souøadnicemi a vazbami hran na prùseèík.
302 \s{Fortunùv~algoritmus}
306 \:Pøipravíme si haldu $H$ a vlo¾íme do ní v¹echny místní události.
308 \:Pøipravíme pobøe¾ní linii $P \leftarrow 0$.
310 \:Dokud existuje $h \leftarrow DeleteMin(H)$:
312 \::Je-li na øadì místní událost:
314 \:::Najdeme prùseèík s $P(FindX(P))$.
316 \:::Vlo¾íme do $P$ novou parabolu.
318 \:::Poznamenáme do $D$ vznik hran.
320 \:::Pøepoèítáme kru¾nicové události.
322 \::Je-li na øadì kru¾nicová událost:
324 \:::Sma¾eme oblouk z $P$.
326 \:::Poznamenáme vznik a zánik do $D$.
328 \:::Pøepoèítáme kru¾nicové události.
334 Poèet místních událostí je roven $n$ (na ka¾dé místo narazíme právì jednou).
335 Poèet kru¾nicových událostí není vìt¹í ne¾ $n$, proto¾e kru¾nicová událost sma¾e
336 parabolu a ty vznikají jen pøi místních událostech, tak¾e kru¾nicových událostí
337 není více ne¾ místních. Speciálnì z toho plyne, ¾e velikost pobøe¾ní linie je
338 v¾dy lineární, proto¾e s ka¾dou místní událostí pøibudou dva úseky do pobøe¾ní
339 linie, tak¾e velikost pobøe¾ní linie je maximálnì $2n$. Velikost haldy je pak
340 také $2n$, tak¾e pak operace urèitì zvládneme v èase $\O(\log n)$. Jeliko¾
341 diagram je lineárnì velký tak i jeho struktura je lineárnì velká. Operace se
342 strukturami nás stojí nejvíce $\O(\log n)$. Tak¾e místní i kru¾nicové události
343 zvládneme v èase $\O(\log n)$ na jednu na konstantním poètu struktur. Halda má
344 velikost $2n$, tak¾e maximálnì provedeme $\O(2n\log n)$ operací.
345 Celý algoritmus potøebuje na~inicializaci maximálnì $\O(n \log n)$ (i kdybychom
346 ji dìlali neefektivnì) a $\O(2n\log n)$ výpoèet.
348 Pokud tedy shrneme v¹echny na¹e odhady, pak èasová slo¾itost algoritmu je
349 $\O(n \log n)$ a prostorová $\O(n)$.
355 1) Pøipravíme si haldu $H$ a vlo¾íme do ní v¹echny místní události.
357 2) pøipravíme pobøe¾ní linii P <- 0 } O(n\log n)
359 3) pøipraváme reprezentaci diagramu D /
361 4) dokud existuje h <- DeleteMin(H)
363 5) je-li na øadì místní událost: ----
365 a) najdeme prùseèík s P(FindX(P)) \
367 b) vlo¾íme do P novou parabolu \
369 c) poznamenáme do D vznik hran } O(\log n)
371 d) pøepoèítáme kru¾nicové události / } <= 2n
373 6) je-li na øadì kru¾nicová událost:
375 a) sma¾eme oblouk z P \
377 b) poznamenáme vznik a zánik do D } O(\log n)
379 c) pøepoèítáme kru¾nicové události / ----