+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)$.