9-geom/9-geom.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{9}{Geometrické algoritmy}{(B. Maslowski, J. Návrat, M. Sta¹a)}
   4
   5 \>Budeme se teï bavit o geometrických problémech v~rovinì. Vìt¹ina algoritmù, které zde uvedeme má své obdoby sice i pro prostory vy¹¹í nebo ni¾¹í dimenze. Jednorozmìrné pøípady ale bývají triviální a vícerozmìrné jsou zase vìt¹inou moc slo¾ité.
   6 Budeme se tedy zabývat tím, jak tyto problémy øe¹it v~dimenzi dva (v~Euklidovské rovinì).
   7
   8
   9 \h{Hledání konvexního obalu}
  10 Ptáte se o co pùjde? Zkusme si to pøiblí¾it na problému ledních medvìdù :)
  11 {\I Lední medvìdi si po dlouhé dobì zmapovali vody severního moøe a zjistili pøesnì místa, kde se nacházejí jejich oblíbené ryby. No a proto¾e to jsou medvìdi chytøí, rozhodli se v¹echny tyto rybky pochytat najednou do jedné velké sítì. A problém, který tady mají, je následující: jaký nejmen¹í obvod mù¾e mít taková sí», aby se dovnitø ve¹ly je¹tì v¹echny rybky?!}
  12
  13 Neboli budeme øe¹it, jak nìjakou zadanou mno¾inu bodù v~rovinì obalit co nejkrat¹í uzavøenou køivkou, do které by se je¹tì v¹echny body ve¹ly.
  14
  15 Intuice nám napovídá ¾e výsledek bude nìjaký konvexní\foot{Mno¾ina bodù v~rovinì je konvexní útvar, pokud platí ¾e pro ka¾dé dva body této mno¾iny je úseèka spojující tyto dva body také celá v~této mno¾inì} mnohoúhelník, který bude mít vrcholy v~nìkterých uvedených bodech. Ostatní vrcholy pak budou buï nìkde na hranách mnohoúhelníku, nebo uvnitø.
  16
  17 \>Mo¾ná by se teï hodilo pøedvést názornì jak vypadají nejmen¹í konvexní obaly:
  18
  19 \itemize\ibull
  20 \:konvexní obal prázdné mno¾iny je prázdná mno¾ina
  21 \:konvexní obal 1 bodu je bod samotný
  22 \:konvexní obal 2 bodù je úseèka spojující tyto body
  23 \:konvexní obal 3 bodù je trojúhleník s vrcholy v~tìchto bodech
  24 \:konvexní obal 4 bodù \dots to u¾ je slo¾itìj¹í
  25 \endlist
  26 Konvexní obaly 4 a více bodù, jak si mù¾em v¹imnout, u¾ nejsou jednoznaèné. Pro $N$-prvkovou mno¾inu bude konvexní obal mnohoúhelník se tøemi a¾ $N$ vrcholy.
  27
  28 Jeden dobrý zpùsob jak tento konvexní obal sestrojit se nazývá {\I Zametání roviny.}
  29
  30 Algoritmus funguje tak ¾e si v~rovinì zvolíme nìjaký smìr, a v~tomto smìru zaèneme posouvat pøímku.
  31 Budeme takto potkávat body které le¾í v~na¹í mno¾inì.
  32 v~ka¾dém okam¾iku budeme chtít, aby v~té èásti kterou jsme ji¾ zametli, jsme u¾ mìli spoèítaný konvexní obal. V¾dycky kdy¾ pak zametací pøímkou narazíme na  nový bod, tak si u¾ jen rozmyslíme jak ho do toho konvexního obalu pøidat.
  33
  34 BÚNO tady v¹ude bereme body v~obecné poloze, tedy takové, ¾e ¾ádné tøi nele¾í na~jedné pøímce. Dál taky budem pøedpokládat ¾e budeme zametat ve smìru $X$-ové osy a ¾e v¹echny body mají rùznou $X$-ovou souøadnici.
  35
  36 Jde také vidìt ¾e bod s nejmen¹í a nejvìt¹í $X$-ovou souøadnicí bude le¾et v~konvexním obalu.
  37
  38 \s{Algoritmus:}
  39 \algo
  40 \:Setøídíme body podle jejich $X$-ové souøadnice.
  41 \:Vezmem první tøi body a sestrojíme jejich konvexní obal.
  42 \:Opakuj: Najdeme dal¹í bod a podíváme se jestli ho mù¾eme do konvexního obalu rovnou pøidat:
  43 \::Pokud jej mù¾eme rovnou pøidat, tak jej pøidáme.
  44 \::Pokud jej pøidat rovnou nemù¾eme, pak je potøeba nejdøív~nìjaké body odzadu odebrat a pak teprv~pøipojit ná¹ nový bod .
  45 \endalgo
  46
  47 Ka¾dá iterace tedy bude probíhat tak, ¾e nìjaké body z pùvodního konvexního obalu pozapomínáme a pøidáme ná¹ nový bod.
  48 Aby se to lépe popisovalo, tak celý konvexní obal rozdìlíme na {\I horní obálku} a {\I dolní obálku.}
  49
  50 :: Obrazek obalek ::
  51
  52 Vidíme teï, ¾e dolní obálka je nìjaká lomená èára, která zatáèí doleva. Horní obálka zatáèí doprava.
  53 v~na¹em algoritmu si budeme obálky pamatovat jako seznamy vrcholù. Kdy¾ narazíme na nový vrchol tak
  54
  55 \s{Algoritmus:}
  56 \algo
  57 \:Setøídíme body podle souøadnice $x$, dostaneme mno¾inu bodù $b_1~-~b_n$.
  58 \:Spoèítáme konvexní obal ${b_1, b_2, b_3}$, z toho získáme horní a dolní obálku.
  59 \:Pro $b$ postupnì zpracováváme $b_3 - b_n$:
  60 \::Pøepoèítáme Horní obálku:
  61 \:::Dokud $(\vert H\vert \geq 2)$ a úhel $(H[-2], H[-1], b)$ je orientovaný doleva:
  62 \::::Odebereme poslední prvek z obálky.
  63 \:::Pøidáme do obálky nový vrchol.
  64 \::Pøepoèítáme dolní obálku:
  65 \:::Dokud $(\vert D\vert \geq 2)$ a úhel $(D[-2], D[-1], b)$ je orientovaný doprava:
  66 \::::Odebereme poslední prvek z obálky.
  67 \:::Pøidáme do obálky nový vrchol.
  68 \endalgo
  69
  70 Setøídit body podle $X$-ové souøadnice a sestrojit konvexní obal prvních tøech bodù stihneme v~èase $\O(n \log n)$. Zbytek pak u¾ udìláme dokonce v~èase lineárním $\O(n)$. Tedy
  71
  72 \s{Vìta:} Konvexní obal doká¾eme sestrojit v~èase $\O(n \log n)$.
  73
  74 \h{Voroného diagramy}
  75
  76 Pøed tím, ne¾ vás vystra¹ím nìjakou definicí, si øekneme, co jsi pod tímto, na první pohled ne zøejmým pojmem, pøedstavit. Mìjme mno¾inu teèek $T$ rozmístìných náhodnì po papíru. Ke ka¾dému bodu nakreslíme okraje tak, aby vniklá plo¹ka obsahovala body, které jsou nejblí¾e právì té na¹í vybrané teèce. Samozøejmì "sousední" teèky budou mít tyto hranice spoleèné. Výsledkem na¹eho dlouhého sna¾ení pak bude právì Voroného diagram. V dal¹ích odstavcích se budeme zajímat o to, jak takový útvar správnì popsat, jak ho sestrojit a jaké datové struktury k tomu pou¾ít.
  77
  78 \s{Definice:} Voronoi diagram pro koneènou mno¾inu $M = \{m_1, \dots, m_n\} \in {\bb R}^2$ míst je systém mno¾in $1..M_n$ takových, ¾e pro v¹echny $i$ a $j$ a pro v¹echny $x \in M_i$ je vzdálenost $x$ a $m_i$ men¹í nebo rovna vzdálenosti $x$ a $m_j$ a zároveò sjednocení $M_i$ pøes v¹echna $i$ je celý prostor ${\bb R}^2$, neboli:
  79
  80 $$d(x,m_i) \leq d(x,m_j) \wedge {\bigcup}_i M_i = {\bb R}^2.$$
  81
  82 Voroného diagram se tedy skládá z nìjakých bodù, oblastí a hran, které ty oblasti oddìlují.
  83
  84 \s{Pozorování:}
  85 \itemize\ibull
  86 \:Pro v¹echny $i$ je $M_i$ ohranièena konvexní lomenou èarou, tak¾e oblasti mají tvar konvexních mnohoúhelníkù, ale je mo¾né, ¾e jsou otevøené do nekoneèna.
  87 \:Pro ka¾dou hranu $h$ ve Voroného diagramu existuje $i$ a $j$ takové, ¾e kdy¾ $x \in H$, pak vzdálenost $d(x,m_i) = d(x,m_j)$.
  88
  89 Øekneme, ¾e vrchol je takové místo, kde se potkávají alespoò dvì hrany.
  90
  91 \:Pro ka¾dý vrchol $v$ Voroného diagramu existují alespoò tøi místa le¾ící
  92 na kru¾nici se støedem $v$.
  93 \figure{body.eps}{Body na kru¾nici.}{3in}
  94 \:Poèet vrcholù a hran je lineární.
  95 \:Poèet krajních oblastí je tak velký, jak velký je konvexní obal té zadané mno¾iny. (je to dobré vìdìt, ale asi to nebudeme potøebovat)
  96 \endlist
  97
  98 Pojïme teï vymyslet, jak takový diagram utøídit. Mohli bychom zkonstruovat v¹echny dìlící pøímky a poslepovat je, ale vznikl by nám kvadratický algoritmus a to nám nemù¾e staèit.
  99
 100 Mluvili jsme o zametání roviny a tak bychom tento trik mohli vyu¾ít právì pøi
 101 øe¹ení na¹eho problému. Ov¹em tentokrát má zametání jeden podstatný háèek. Kdy¾
 102 si vezmeme nìjakou zametací pøímku a pojedeme s ní od shora dolù, tak nad ní
 103 máme u¾ nìjakou zkonstruovanou èást diagramu a kdy¾ narazíme na dal¹í bod, tak
 104 se nám mù¾e právì tato èást pomìrnì slo¾itì zmìnit. Pomù¾eme si malým trikem.
 105 Nebudeme pova¾ovat ten diagram za uplnì hotový, ale pro ka¾dý bod nad pøímkou
 106 mno¾inu v¹ech bodù, které mají blí¾e k tomu pøíslu¹nému bodu ne¾ k té pøímce.
 107 To tvoøí nìjakou parabolu. Tak¾e v této oblasti u¾ je bezpeèno, v¹echno co jsme
 108 spoèítali uvnitø této paraboly nám u¾ nikdo nepokazí (ani nevylep¹í). Vezmeme si
 109 tedy dolní obálku tìchto parabol.
 110 \figure{pobrezi.eps}{Pobøe¾ní linie.}{3in}
 111 Pobøe¾í je nìjaká posloupnost parabolických obloukù s tím, ¾e nejlevìj¹í a
 112 nejpravìj¹í jdou do nekoneèna.
 113
 114 Kdykoliv tedy narazíme na nìjaký bod, tak nám mu¾e ovlivnit u¾ jen tu èást diagramu
 115 pod pobøe¾ím. Dostáváme se tedy k tomu, co se dìje, kdy¾ hýbeme zametací pøímkou.
 116 Pakli¾e nenará¾íme na ¾ádné body, tak se v podstatì nedìje nic pøíli¹ zajímavého.
 117 Zajímavá situace nastává a¾ tehdy, narazímeli na dal¹í bod. V tom okam¾iku vzniká
 118 nová parabola. V tuto chvíli je znaènì degenerovaná. Je to toti¾ vlastnì zatím jen
 119 polopøímka kolmá na na¹i  øídící pøímku. S dal¹ím pohybem se zaène parabola rozevírat.
 120 V¹imnìme si, ¾e prùnik té na¹í pøímky a pobøe¾í je vlastnì vrchol ve Voroného diagramu.
 121 Mù¾e nastat je¹tì jeden problém. Nìjaká parabola se mù¾e natolik rozevøít, ¾e pohltí
 122 jiné.
 123
 124 Shrneme-li na¹e úvahy, mù¾ou se dít celkem tøi vìci. Jedna z nich je posun pøímky.
 125 To se vlastnì dìje poøád. Nemìní se nám rif pobøe¾í a prùseèíky parabol nám kreslí
 126 hrany. To mù¾eme poèítat najednou. Navíc nejen ¾e bychom mohli s pøímkou skoèít
 127 o nìjaké epsilon, ale mi dokonce mù¾eme skoèit o poøádný kus a prostì pouze dopoèítat,
 128 jak se nám zmìnilo pobøe¾í a co se nám vykreslilo.
 129
 130 Pokud tedy narazíme na bod, tak musíme najít místo, kde to na¹e pobøe¾í rozetnou
 131 a kam vklínit dal¹í výbì¾ek (parabolu). Takovéto události budeme øíkat místní událost.
 132 Pokud se pohybujeme v obecné poloze, tak se nám nestane, ¾e bychom narazili na prùseèík.
 133 \figure{mistni.eps}{Místní událost.}{3in}
 134
 135 Poslední situace, která tedy mù¾e nastat je, ¾e nám nìjaký parabola schová za jiné.
 136 Kouknìme se na obrázek, fialový bod le¾í na ka¾dé parabole. Speciálnì tedy ta tøi
 137 ohniska parabol jsou vzdálena stejnì a le¾í na kru¾nici. Stane se nám to pravì tehdy,
 138 kdy¾ se nám zametací pøímka dotkne kru¾nice, která je urèena právì tìmito tøemi
 139 ohnisky. Tuto událost nazveme kru¾nicová. Pojïme si to ukázat lépe na následujících
 140 dvou obrázcích. První pøedstavuje situaci pøed kru¾nicovou událostí, druhý je pak
 141 právì ona záhadná kru¾nicová událost.
 142 \figure{kruznicova.eps}{Pøed kru¾nicovou událostí.}{3in}
 143 \figure{kruznicovakonec.eps}{Kru¾nicová událost.}{3in}
 144
 145
 146 \s{Datové struktury}
 147
 148 Budeme potøebovat haldu událostí (místních i kru¾nicových dohromady), ta nám
 149 zabere $\O(\log n)$ pamìti.
 150
 151 Dále bude zapotøebí si udr¾ovat na¹i pobøe¾ní linii neboli posloupnost míst
 152 v~ohniscích parabolických obloukù. Zde je potøeba si definovat operace
 153 {\I Insert,Delete} a {\I FindX.} Navíc budeme potøebovat vyhledávací strom nad
 154 prùseèíky s implicitní reprezentací. Zdá se, ¾e je toho hodnì, ale v¹echno to
 155 zvládneme s pamìtí $\O(\log n).$
 156
 157 Poslední datovou strukturou bude samotný diagram, reprezentovaný grafem se
 158 souøadnicemi a vazbami hran na prùseèík.
 159
 160
 161 \s{Fortunùv~algoritmus}
 162 \algo
 163 \:Pøipravíme si haldu $H$ a vlo¾íme do ní v¹echny místní události.
 164 \:Pøipravíme pobøe¾ní linii $P \leftarrow 0$.
 165 \:Dokud existuje $h \leftarrow DeleteMin(H)$:
 166 \::Je-li na øadì místní událost:
 167 \:::Najdeme prùseèík s $P(FindX(P))$.
 168 \:::Vlo¾íme do $P$ novou parabolu.
 169 \:::Poznamenáme do $D$ vznik hran.
 170 \:::Pøepoèítáme kru¾nicové události.
 171 \::Je-li na øadì kru¾nicová událost:
 172 \:::Sma¾eme oblouk z $P$.
 173 \:::Poznamenáme vznik a zánik do $D$.
 174 \:::Pøepoèítáme kru¾nicové události.
 175 \endalgo
 176
 177
 178 \s{Slo¾itost:}
 179 Poèet místních událostí je roven $n$ a poèet kru¾nicových událostí není vìt¹í ne¾
 180 $n$ (s ka¾dou místní událostí zanikne kru¾nicová), neboli velikost $P$ není vìt¹í
 181 ne¾ $2n$, a tedy je v¾dy lineární. Zároveò velikost $H$ není vìt¹í ne¾ $2n$,
 182 proto¾e aèkoliv~poèet místních událostí je $n$, tak v~$H$ je záznam pro ka¾dou
 183 trojici, a tedy v~$H$ je maximálnì $2n$ událostí najednou. Zbývá nám tedy zjistit
 184 velikost diagramu $D$, ale ten se urèitì vejde do $\O(n)$ pamìti.
 185
 186 Pokud tedy shrneme v¹echny na¹e odhady, pak èasová slo¾itost algoritmu je
 187 $\O(n \log n)$ a prostorová $\O(n)$.
 188
 189
 190 \bye
 191
 192
 193 -------------------
 194
 195 1) Pøipravíme si haldu $H$ a vlo¾íme do ní v¹echny místní události.
 196 2) pøipravíme pobøe¾ní linii P <- 0                               } O(n*log n)
 197 3) pøipraváme reprezentaci diagramu D                            /
 198 4) dokud existuje h <- DeleteMin(H)
 199 5)    je-li na øadì místní událost:                         ----
 200         a) najdeme prùseèík s P(FindX(P))   \
 201         b) vlo¾íme do P novou parabolu       \
 202         c) poznamenáme do D vznik hran        } O(log n)
 203         d) pøepoèítáme kru¾nicové události   /                   } <= 2n
 204 6)    je-li na øadì kru¾nicová událost:
 205         a) sma¾eme oblouk z P              \
 206         b) poznamenáme vznik a zánik do D   } O(log n)
 207         c) pøepoèítáme kru¾nicové události /                ----
 208
 209
 210
 211
 212 \bye