i. Konvexní obal v rovině
Konvexní množiny a konvexní obaly v rovině. Připomeňme si, že množina K v rovině je konvexní, jestliže s každými dvěma body obsahuje i úsečku, kterou určují.
OBR 1.1 Konvexní a nekonvexní množina
Každý bod r na úsečce pq lze zapsat jako tzv. konvexní kombinaci bodů p a q:
r = Xp+(l-X)q,     kde A G [0,1]. Pro souřadnice (rx,ry) bodu r to znamená
rx =^Px + (1 - A)^,
Ty   =\py  +   (1   - \)qy.
Průnik konvexních množin je evidentně opět konvexní množina. Konvexní obal CH(P) množiny P v rovině je nej menší konvexní množina obsahující množinu P, množinově to lze zapsat takto:
CH(P) f] K.
kdp konvexní
My se budeme zabývat algoritmy, které efektivně najdou konvexní obal pro konečnou množinu P. V tomto případě bude
CH(P) f] H.
hdp polorovina
Přitom se stačí omezit na poloroviny určené dvojicí bodů z množiny P, v nichž leží i zbývající body množiny P. Konvexním obalem konečné neprázdné množiny s aspoň dvěma body je tedy konvexní mnohoúhelník, který může zdegenerovat na úsečku.
Naivní algoritmus. V této sekci si ukážeme, že pouhá znalost matematické definice ještě nestačí k vytvoření dobrého algoritmu. Algoritmus bude hledat orientované úsečky pq, které tvoří hranici konvexního obalu orientovanou ve směru hodinových ručiček. Je založen na tom, že v tomto případě neleží nalevo od orientované přímky pq žádný bod množiny P.
OBR 1.2 Nalevo od orientované přímky pq neleží žádný bod množiny P.
Skutečnost, že bod r leží nalevo od orientované přímky pq lze matematicky zachytit podmínkou na determinant, jehož řádky tvoří souřadnice vektorů q — p a r — p:
det(fc-p* qyzpy) >o.
\J*x      Px    fy      Py J
Tento determinant matice 2 x 2 lze zapsat i jako determinant matice 3x3
2
ALGORITMUS 1 z pseudo.pdf
Časová náročnost tohoto algoritmu při n bodech na vstupuje 0(n3), neboť procházíme všechny orientované přímky a pro každou testujeme, kde leží zbývající body. Dalším nedostatkem je skutečnost, že algoritmus je nestabilní. Jestliže tři body p±, p2, P3 leží na jedné přímce, může nastat situace, kdy orientované úsečky P1P2, P2P3 a P1P3 jsou prvky množiny hraničních úseček E. Pak ale může nastat problém s jejich uspořádáním do posloupnosti ve směru hodinových ručiček.
OBR 1.3 Tři body množiny P na jedné hraniční úsečce.
Lepší algoritmus. Daleko lepší výsledek dostaneme, když body množiny P před hledáním hraničních úseček konvexního obalu vhodným způsobem uspořádáme. Použijeme lexikografické uspořádání bodů nejdřív podle souřadnice x a potom podle souřadnice y. Tedy
p < q    právě když px < qx nebo (px = qy a py < qy). V tomto uspořádání označme body od nejmenšího k největšímu
Pl < P2 < P3 < ■ ■ ■ < Pn-l < Pn-
Body pi, který je "nejvíce vlevo", a bod pn, který je "nejvíce vpravo", tedy určitě leží na hranici konvexního obalu a rozdělují ji na horní a dolní část. Abychom se vyhnuli dlouhým formulacím, budeme poněkud nepřesně mluvit o horním a dolním konvexním obalu, místo abychom mluvili o horní a dolní části hranice konvexního obalu.
OBR 1.4 Horní (modrý) a dolní (zelený) konvexní obal.
Uspořádání bodů horní hranice konvexního obalu ve směru hodinových ručiček koresponduje s jejich lexikografickým uspořádáním. Proto náš algoritmus bude postupně hledat horní konvexní obal množin
Pí = {Pl,P2,---,Pi}
od i = 2 do i = n. Podobným způsobem pak bude postupně hledat dolní konvexní obal množin
{Pn-i,Pn-l+l ■ ■ ■ ,pn-l,Pn}
pro i = 1 do n — 1.
Nechť £ je lexikograficky uspořádaný seznam vrcholů horního konvexního obalu množiny P«. Ten vždy obsahuje body p\ a Nyní změníme seznam C tak, aby byl tvořen vrcholy horního konvexního obalu množiny P«+i. V něm musí být lexikograficky největší bod Pi+i, proto jej přidáme do C
Body nepatřící do horního konvexního obalu množiny Pi+\ vyloučíme ze seznamu C postupně takto: Vezmeme v C poslední tři vrcholy p j < pi < Pí+±. Jestliže bod pi+1 leží vpravo od orientované přímky PjPi, budeme říkat, že body pj, pi a pi+1 tvoří zatáčku vpravo. V tomto případě seznam C měnit nebudeme, neboť body množiny Pi-i leží vpravo od orientované přímky pipi+1. Máme tedy seznam vrcholů horního konvexního
3
obalu množiny Pi+Í a můžeme začít hledat seznam vrcholů horního konvexního obalu množiny Pj+2, je-li i + 2 < n.
OBR 1.5 Zatáčka vpravo.
Jestliže body pj, pi a pi+i netvoří zatáčku vpravo, pak ze seznamu C vyloučíme prostřední z nich, tedy Pí. Jestliže totiž Pí leží na úsečce PjPí+i, tak ho k popisu horního konvexního obalu nepotřebujeme, i když na něm leží. Jestliže pi+1 leží vlevo od orientované přímky PjPi, pak Pí leží vpravo od orientované přímky PjPí+i a není tedy v horním konvexním obalu množiny Pj+i.
OBR 1.6 Situace, kdy poslední tři body v C netvoří zatáčku vpravo.
Po vyloučení bodu pi ze seznamu C vezmeme opět poslední tři body tohoto seznamu, pokud existují, a provedeme s nimi stejnou proceduru. Tu provádíme tak dlouho, až
• v seznamu C zůstanou pouze dva body,
• nebo poslední tři body seznamu C tvoří zatáčku vpravo.
Tím je hledání seznamu vrcholů horního konvexního obalu pro množinu P« ukončeno. Tento postup si ilustrujme na příkladu pomocí následující animace.
ANIMACE 1.1
Vrcholy dolního konvexního obalu získáme analogicky.
Pseudokód a časová náročnost. Výše uvedený slovní popis můžeme formalizovat pomocí následujícího pseudokódu:
ALGORITMUS 2 z pseudo.pdf
Věta 1.1. Výše uvedený algoritmus je korektní a jeho časová náročnost v závislosti na počtu bodů množiny P je 0(nlogn).
Důkaz. Důkaz, že pomocí algoritmu dostaneme seznam vrcholů konvexního obalu množiny P uspořádaný ve směru hodinových ručiček se redukuje na důkaz, že algoritmus nám dá seznam vrcholů horního, popř. dolního konvexního obalu seřazený lexikograficky. Důkaz pro horní obal se provádí induktivně: Ukážeme, že ze seznamu vrcholů pro horní konvexní obal množiny Pj vytvoří algoritmus seznam vrcholů horního konvexního obalu množiny Pj+i. To provádíme stejnými úvahami jako při slovním popisu algoritmu. Prakticky zaměřeného čtenáře jimi již nebudeme unavovat. Teoreticky zaměřený čtenář se je může pokusit zvládnout sám.
Co se týče časové náročnosti, tak prvý krok, uspořádání n bodů v lexikografickém uspořádání trvá, jak je dobře známo, čas 0(nlogn). Ukážeme, že zbývající část algoritmu zabere pouze čas 0(n). Každý z bodů množiny P do seznamu C pro horní konvexní obal vkládáme právě jednou a nejvýše jednou jej vyndáváme. Tyto akce provedeme v konstantním čase. Tedy časová náročnost vytvoření seznamu musí být úměrná počtu bodů.
4
Čtenář jistě sám přijde na řadu způsobů, jak výše uvedený algoritmus vylepšit. Nicméně žádné z nich časovou náročnost nevylepší na nějaký odhad lepší než 0(n logn).
□
Jiný algoritmus. Pro konvexní obal v rovině existuje řada dalších algoritmů. Naznačíme jeden z nich, který je vhodný použít v případě, pokud dopředu víme, že počet vrcholů konvexního obalu bude vzhledem k počtu bodů množiny P malý. Postup algoritmu připomíná balení, proto se nazývá Gift wrapping.
Pro zjednodušení předpokládejme, že žádné tři body neleží v přímce. Nejdříve najdeme bod množiny P nejvíce vlevo (přesněji, nejmenší ve výše uvedeném lexiko-grafickém uspořádání) a označme jej p\. Z bodu p\ vedeme přímky do dalších bodů množiny P a počítáme jejich směrnice. Nechť p2 je takový bod, že p\p2 má z těchto přímek největší směrnici. Nyní z bodu p2 vedeme spojnice do zbývajících n — 2 bodů množiny P. Z nich vybereme bod p3 tak, aby konvexní úhel Zpľp2p3 je největší. Tímto způsobem pokračujeme, až se dostaneme zpět do bodu p\. Tím jsme zakončili balení množiny P do konvexního obalu. Je-li konvexní obal fc-úhelník, je časová náročnost tohoto algoritmu 0(kn). V každém z k vrcholů strávíme čas 0(n).
ANIMACE 1.2