\input lecnotes.tex
-\prednaska{7}{Geometrické algoritmy}{(P. Klavík)}
+\prednaska{7}{Geometrické algoritmy}{(sepsal Pavel Klavík)}
\>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í
a naopak pro vy¹¹í dimenze jsou velice komplikované. Rovina je proto rozumným kompromisem mezi obtí¾ností a zajímavostí.
-Celou kapitolou nás bude provázet pohádka ze ¾ivota letních medvìdù. Pokusíme se vyøe¹it jejich \uv{ka¾dodenní} problémy~\dots
+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
\h{Hledání konvexního obalu}
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
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.}
-\figure{7-geom5_rybi_motivace.eps}{Problém ledních mìdvìdù: Jaký je nejmen¹í obvod sítì?}{2.5in}
+\figure{7-geom5_rybi_motivace.eps}{Problém ledních mìdvìdù: Jaký je nejmen¹í obvod sítì?}{3in}
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í},
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é
$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
kroku pøidat do obalu $k$-tý nejlevìj¹í bod. Zbývá si jen rozmyslet, jak pøesnì tento bod pøidat.
-Poslední bod napojíme na nejbli¾¹í bod konvexního obalu, který je nad ním a pod ním. Èasto se v¹ak stane, ¾e obal pøestane být konvexní. To se dá v¹ak
-snadno napravit, staèí odebírat pøedcházející body tak dlouho, dokud nezískáme konvexní obal. Pøíklad pøidání bodu je na obrázku ní¾e. Mnohdy je
-potøeba odebrat i více ne¾ jeden bod.
+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
+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èí
+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
+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.
\figure{7-geom2_pridani_bodu.eps}{Pøidání bodu do konvexního obalu.}{4.5in}
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
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í
-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)$.
+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 v
+$\O(n)$.
\s{Algebraický dodatek:} Existuje jednoduchý postup, jak zjistit orientaci úhlu? Uká¾eme si jeden zalo¾ený na lineární algebøe. Budou se hodit
-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,
-¾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
-matic $2 \times 2$.
+vlastnosti determinantu. Absolutní hodnota determinantu je objem rovnobì¾nostìnu urèeného øádkovými vektory matice. Dùle¾itìj¹í v¹ak je, ¾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 matic $2
+\times 2$.
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
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$
\figure{7-geom4_determinant.eps}{Jak vypadají determinanty rùzných znamének v~rovinì.}{4.6in}
-\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,
-funguje v~èase $\O(n \log h)$, kde $h$ je poèet bodù le¾ících v~konvexním obalu, a pøitom je pøekvapivì jednoduchý. Zde si naznaèíme, jak tento
-algoritmus funguje.
+\s{©lo by to vyøe¹it rychleji?} Také vám vrtá hlavou, zda existují rychlej¹í algoritmy? Na závìr si uká¾eme nìco, co na pøedná¹ce nebylo.\foot{A také
+se nebude zkou¹et.} Nejrychlej¹í známý algoritmus, jeho¾ autorem je T.~Chan, 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 algoritmus funguje.
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
\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
-algoritmu. To doká¾eme pro jednu v~èase $\O(h \log h)$ a pro v¹echny v~èase $\O(n \log h)$. Nakonec vezmeme tyto konvexní obaly a pomocí jiného
-algoritmu je v~èase $\O(n \log h)$ spojíme do konvexního obalu celé mno¾iny.
+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í
+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í:
+
+\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í
+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é
+z polorovin.}
+
+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
+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
+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
+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
+vybrat následníka, co¾ doká¾eme v èase $\O(n)$. Celková slo¾itost algoritmu je tedy $\O(n \cdot h)$.
+
+\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}
+
+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é
+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.
+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.
+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í
+konvexního obalu. Detaily si rozmyslí ètenáø sám.
+
+È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
+$\O({n \over h} \log h)$. Celý obal nalezneme ve slibovaném èase $\O(n \log h)$.
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$,
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ì
projects / ads2.git / blobdiff