7-geom/7-geom.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{7}{Geometrické algoritmy}{(P. Klavík)}
   4
   5 \>Uká¾eme si nìkolik základních algoritmù na øe¹ení geometrický problémù v~rovinì. Proè zrovna v~rovinì? Inu, jednorozmìrné problémy bývají triviální
   6 a naopak pro vy¹¹í dimenze jsou velice komplikované. Rovina je proto rozumným kompromisem mezi obtí¾ností a zajímavostí.
   7
   8 Celou kapitolou nás bude provázet pohádka ze ¾ivota ledních medvìdù. Pokusíme se vyøe¹it jejich \uv{ka¾dodenní} problémy~\dots
   9
  10 \h{Hledání konvexního obalu}
  11
  12 {\I Daleko na severu ¾ili lední medvìdi. Ve vodách tamního moøe byla hojnost ryb a jak je známo, ryby jsou oblíbenou pochoutkou ledních medvìdù.
  13 Proto¾e medvìdi z~na¹í pohádky rozhodnì nejsou ledajací a ani chytrost jim neschází, rozhodli se v¹echny ryby pochytat. Znají pøesná místa výskytu
  14 ryb a rádi by vyrobili obrovskou sí», do které by je v¹echny chytili. Pomozte medvìdùm zjistit, jaký nejmen¹í obvod taková sí» mù¾e mít.}
  15
  16 \figure{7-geom5_rybi_motivace.eps}{Problém ledních mìdvìdù: Jaký je nejmen¹í obvod sítì?}{3in}
  17
  18 Neboli v~øeèi matematické, chceme pro zadanou mno¾inu bodù v~rovinì nalézt její konvexní obal. Co je to konvexní obal? Mno¾ina bodù je {\I konvexní},
  19 pokud pro ka¾dé dva body obsahuje i celou úseèku mezi nimi. {\I Konvexní obal} je nejmen¹í konvexní podmno¾ina roviny, která obsahuje v¹echny zadané
  20 body.\foot{Pamatujete si na lineární obaly ve vektorových prostorech? Lineární obal mno¾iny vektorù je nejmen¹í vektorový podprostor, který tyto
  21 vektory obsahuje. Není náhoda, ¾e tato definice pøipomíná definici konvexního obalu. Na druhou stranu ka¾dý vektor z~lineárního obalu lze vyjádøit
  22 jako lineární kombinaci daných vektorù. Podobnì platí i pro konvexní obaly, ¾e ka¾dý bod z~obalu je konvexní kombinací daných bodù. Ta se li¹í od
  23 lineární v~tom, ¾e v¹echny koeficienty jsou v~intervalu $[0,1]$ a navíc souèet v¹ech koeficientù je $1$. Tento algebraický pohled mù¾e mnohé vìci
  24 zjednodu¹it. Zkuste si dokázat, ¾e obì definice konvexního obalu jsou ekvivalentní.} Z~algoritmického hlediska nás v¹ak bude zajímat jenom jeho
  25 hranice, kterou budeme dále oznaèovat jako konvexní obal.
  26
  27 Na¹ím úkolem je nalézt konvexní obal koneèné mno¾iny bodù. To je v¾dy konvexní mnohoúhelník, navíc s~vrcholy v~zadaných bodech. Øe¹ením problému tedy
  28 bude posloupnost bodù, které tvoøí konvexní obal. Pro malé mno¾iny je konvexní obal nakreslen na obrázku, pro více bodù je v¹ak situace mnohem
  29 slo¾itìj¹í.
  30
  31 \figure{7-geom1_male_obaly.eps}{Konvexní obaly malých mno¾in.}{3in}
  32
  33 Pro jednoduchost budeme pøedpokládat, ¾e v¹echny body mají rùzné $x$-ové souøadnice. Tedy utøídìní bodù zleva doprava je urèené jednoznaènì.\foot{To si
  34 mù¾eme dovolit pøedpokládat, nebo» se v¹emi body staèí nepatrnì pootoèit. Tím konvexní obal urèitì nezmìníme. Av¹ak jednodu¹¹í øe¹ení je naprogramovat
  35 tøídìní lexikograficky (druhotnì podle souøadnice $y$) a vyøadit identické body.} Tím máme zaji¹tìné, ¾e existují dva body, nejlevìj¹í a
  36 nejpravìj¹í, pro které platí následující invariant:
  37
  38 \s{Invariant:} Nejlevìj¹í a nejpravìj¹í body jsou v¾dy v~konvexním obalu.
  39
  40 Algoritmus na nalezení konvexního obalu funguje na následujícím jednoduchém principu, kterému se nìkdy øíká {\I zametání roviny}. Procházíme body
  41 zleva doprava a postupnì roz¹iøujeme doposud nalezený konvexní obal o~dal¹í body. Na zaèátku bude konvexní obal jediného bodu samotný bod. Na konci
  42 $k$-tého kroku algoritmu známe konvexní obal prvních $k$ bodù. Kdy¾ algoritmus skonèí, známe hledaný konvexní obal. Podle invariantu musíme v~$k$-tém
  43 kroku pøidat do obalu $k$-tý nejlevìj¹í bod. Zbývá si jen rozmyslet, jak pøesnì tento bod pøidat.
  44
  45 Pøidání dal¹ího bodu do konvexního obalu funguje, jak je naznaèeno na obrázku. Podle invariantu víme, ¾e bod nejvíc vpravo je souèástí konvexního
  46 obalu. Za nìj napojíme novì pøidávaný bod. Tím jsme získali nìjaký obal, ale zpravidla nebude konvexní. To lze v¹ak snadno napravit, staèí
  47 odebírat body, v obou smìrech podél konvexního obalu, tak dlouho, dokud nezískáme konvexní obal. Na pøíkladu z obrázku nemusíme po smìru hodinových
  48 ruèièek odebrat ani jeden bod, obal je v poøádku. Naopak proti smìru hodinových ruèièek musíme odebrat dokonce dva body.
  49
  50 \figure{7-geom2_pridani_bodu.eps}{Pøidání bodu do konvexního obalu.}{4.5in}
  51
  52 Pro pøípadnou implementaci a rozbor slo¾itosti si nyní popí¹eme algoritmus detailnìji. Aby se lépe popisoval, rozdìlíme si konvexní obal na dvì èásti
  53 spojující nejlevìj¹í a nejpravìj¹í bod obalu. Budeme jim øíkat {\I horní obálka} a {\I dolní obálka}.
  54
  55 \figure{7-geom3_obalky.eps}{Horní a dolní obálka konvexního obalu.}{3.4in}
  56
  57 Obì obálky jsou lomené èáry, navíc horní obálka poøád zatáèí doprava a dolní naopak doleva. Pro udr¾ování bodù v~obálkách staèí dva zásobníky.
  58 V~$k$-tém kroku algoritmu pøidáme zvlá¹» $k$-tý bod do horní i dolní obálky. Pøidáním $k$-tého bodu se v¹ak mù¾e poru¹it smìr, ve kterém obálka
  59 zatáèí. Proto budeme nejprve body z~obálky odebírat a $k$-tý bod pøidáme a¾ ve chvíli, kdy jeho pøidání smìr zatáèení neporu¹í.
  60
  61 \s{Algoritmus:}
  62
  63 \algo
  64
  65 \:Setøídíme body podle $x$-ové souøadnice, oznaème body $b_1, \ldots, b_n$.
  66 \:Vlo¾íme do horní a dolní obálky bod $b_1$: $H = D = (b_1)$.
  67 \:Pro ka¾dý dal¹í bod $b = b_2,\ldots,b_n$:
  68 \::Pøepoèítáme horní obálku:
  69 \:::Dokud $\vert H\vert \ge 2$, $H = (\ldots, h_{k-1}, h_k)$ a úhel $h_{k-1} h_k b$ je orientovaný doleva:
  70 \::::Odebereme poslední bod $h_k$ z~obálky $H$.
  71 \:::Pøidáme bod $b$ do obálky $H$.
  72 \::Symetricky pøepoèteme dolní obálku (s orientací doprava).
  73 \: Výsledný obal je tvoøen body v~obálkách $H$ a $D$.
  74
  75 \endalgo
  76
  77 Rozebereme si èasovou slo¾itost algoritmu. Setøídit body podle $x$-ové souøadnice doká¾eme v~èase $\O(n \log n)$. Pøidání dal¹ího bodu do obálek
  78 trvá lineárnì vzhledem k~poètu odebraných bodù. Zde vyu¾ijeme obvyklý postup: Ka¾dý bod je odebrán nejvý¹e jednou, a tedy v¹echna odebrání trvají
  79 dohromady $\O(n)$. Konvexní obal doká¾eme sestrojit v~èase $\O(n \log n)$, a pokud bychom mìli seznam bodù ji¾ utøídený, doká¾eme to dokonce $\O(n)$.
  80
  81 \s{Algebraický dodatek:} Existuje jednoduchý postup, jak zjistit orientaci úhlu? Uká¾eme si jeden zalo¾ený na lineární algebøe. Budou se hodit
  82 vlastnosti determinantu. Absolutní hodnota determinantu je objem pøíslu¹ného rovnobì¾nostìnu tvoøeného øádkovými vektory matice. Dùle¾itìj¹í v¹ak je,
  83 ¾e znaménko determinantu urèuje \uv{orientaci} vektorù, zda je levotoèivá èi pravotoèivá. Proto¾e ná¹ problém je rovinný, budeme uva¾ovat determinanty
  84 matic $2 \times 2$.
  85
  86 Uva¾me souøadnicový systém v~rovinì, kde $x$-ová souøadnice roste smìrem doprava a~$y$-ová smìrem nahoru. Chceme zjistit orientaci úhlu $h_{k-1} h_k
  87 b$. Polo¾me $\vec u = (x_1, y_1)$ jako rozdíl souøadnic $h_k$ a~$h_{k-1}$ a podobnì $\vec v = (x_2, y_2)$ je rozdíl souøadnic $b$ a~$h_k$. Matice $M$
  88 je definována následovnì:
  89 $$M = \pmatrix{\vec u \cr \vec v} = \pmatrix {x_1&y_1\cr x_2&y_2}.$$
  90 Úhel $h_{k-1} h_k b$ je orientován doleva, právì kdy¾ $\det M = x_1y_2 - x_2y_1$ je nezáporný,\foot{Neboli vektory $\vec u$ a $\vec v$ odpovídají
  91 rozta¾ení a zkosení vektorù báze $\vec x = (1,0)$ a $\vec y = (0,1)$, pro nì¾ je determinant nezáporný.} a spoèítat hodnotu determinantu je jednoduché.
  92 Mo¾né situace jsou nakresleny na obrázku. Poznamenejme, ¾e k~podobnému vzorci se lze také dostat pøes vektorový souèin vektorù $\vec u$ a $\vec v$.
  93
  94 \figure{7-geom4_determinant.eps}{Jak vypadají determinanty rùzných znamének v~rovinì.}{4.6in}
  95
  96 \s{©lo by to vyøe¹it rychleji?} Také vám vrtá hlavou, zda existují rychlej¹í algoritmy? Nejrychlej¹í známý algoritmus, jeho¾ autorem je T.~Chan,
  97 funguje v~èase $\O(n \log h)$, kde $h$ je poèet bodù le¾ících na konvexním obalu, a pøitom je pøekvapivì jednoduchý. Zde si naznaèíme, jak tento
  98 algoritmus funguje.
  99
 100 Algoritmus pøichází s~následující my¹lenkou. Pøedpokládejme, ¾e bychom znali velikost konvexního obalu $h$. Rozdìlíme body libovolnì do $\lceil {n
 101 \over h} \rceil$ mno¾in $Q_1, \ldots, Q_k$ tak, ¾e $\vert Q_i \vert \le h$. Pro ka¾dou z~tìchto mno¾in nalezneme konvexní obal pomocí vý¹e popsaného
 102 algoritmu. To doká¾eme pro jednu v~èase $\O(h \log h)$ a pro v¹echny v~èase $\O(n \log h)$. V druhé fázi spustíme hledání konvexního obalu pomocí
 103 provázkového algoritmu a pro zrychlení pou¾ijeme pøedpoèítané obaly men¹ích mno¾in. Nejprve popí¹eme jeho my¹lenku. Pou¾ijeme následující pozorování:
 104
 105 \s{Pozorování:} Úseèka spojující dva body $a$ a $b$ le¾í na konvexním obalu, právì kdy¾ v¹echny ostatní body le¾í pouze na jedné její
 106 stranì.\foot{Formálnì je podmínka následující: Pøímka $ab$ urèuje dvì poloroviny. Úseèka le¾í na konvexním obalu, právì kdy¾ v¹echny body le¾í v jedné
 107 z polorovin.}
 108
 109 Algoritmu se øíká {\I provázkový}, proto¾e svojí èinností pøipomíná namotávání provázku podél konvexního obalu.  Zaèneme s bodem, který na konvexním
 110 obalu urèitì le¾í, to je tøeba ten nejlevìj¹í. V ka¾dém kroku nalezneme následující bod po obvodu konvexního obalu. To udìláme napøíklad tak, ¾e
 111 projdeme v¹echny body a vybereme ten, který svírá nejmen¹í úhel s poslední stranou konvexního obalu. Novì pøidaná úseèka vyhovuje pozorování a proto
 112 do konvexního obalu patøí. Po $h$ krocích dostaneme zpìt k nejlevìj¹ímu bodu a výpoèet ukonèíme. V ka¾dém kroku potøebujeme projít v¹echny body a
 113 vybrat následníka, co¾ doká¾eme v èase $\O(n)$. Celková slo¾itost algoritmu je tedy $\O(n \cdot h)$.
 114
 115 \twofigures{7-geom6_provazkovy_algoritmus.eps}{Provázkový algoritmus.}{1.25in}{7-geom7_naslednik_pres_konvexni_obal.eps}{Hledání kandidáta v pøedpoèítaném obalu}{2.5in}
 116
 117 Provázkový algoritmus funguje, ale má jednu obrovskou nevýhodu -- je toti¾ ukrutnì pomalý. Ký¾eného zrychlení dosáhneme, pokud pou¾ijeme pøedpoèítané
 118 konvexní obaly. Ty umo¾ní rychleji hledat následníka. Pro ka¾dou z mno¾in $Q_i$ najdeme zvlá¹» kandidáta a poté z nich vybereme toho nejlep¹ího.
 119 Mo¾ný kandidát v¾dy le¾í na konvexním obalu mno¾iny $Q_i$. Vyu¾ijeme toho, ¾e body obalu jsou \uv{uspoøádané}, i kdy¾ trochu netypicky do kruhu.
 120 Kandidáta mù¾eme hledat metodou pùlení intervalu, i kdy¾ detaily jsou malièko slo¾itìj¹í ne¾ je obvyklé. Jak pùlit zjistíme podle smìru zatáèení
 121 konvexního obalu. Detaily si rozmyslí ètenáø sám.
 122
 123 Èasová slo¾itost pùlení je $\O(\log h)$ pro jednu mno¾inu. Mno¾in je nejvý¹e $\O({n \over h})$, tedy následující bod konvexního obalu nalezneme v èase
 124 $\O({n \over h} \log h)$. Celý obal nalezneme ve slibovaném èase $\O(n \log h)$.
 125
 126 Popsanému algoritmu schází jedna dùle¾itá vìc: Ve skuteènosti vìt¹inou neznáme velikost $h$. Budeme proto algoritmus iterovat s~rostoucí hodnotou $h$,
 127 dokud konvexní obal nesestrojíme. Pokud pøi slepování konvexních obalù zjistíme, ¾e konvexní obal je vìt¹í ne¾ $h$, výpoèet ukonèíme. Zbývá je¹tì
 128 zvolit, jak rychle má $h$ rùst. Pokud by rostlo moc pomalu, budeme poèítat zbyteènì mnoho fází, naopak pøi rychlém rùstu by nás poslední fáze mohla
 129 stát pøíli¹ mnoho.
 130
 131 V~$k$-té iteraci polo¾íme $h = 2^{2^k}$. Dostáváme celkovou slo¾itost algoritmu:
 132 $$\sum_{m=0}^{\O(\log \log h)} \O(n \log 2^{2^m}) = \sum_{m=0}^{\O(\log \log h)} \O(n \cdot 2^m) = \O(n \log h),$$
 133 kde poslední rovnost dostaneme jako souèet prvních $\O(\log \log h)$ èlenù geometrické øady $\sum 2^m$.
 134
 135 \bye