Konštrukcia konvexného obalu

Ukážeme si Grahamov algoritmus, ktorý konvexný obal $n$ bodov zostrojí v čase $\Theta(n \log n)$. Toto je takmer optimálne. (Existujú komplikovanejšie algoritmy s o chlp lepšou časovou zložitosťou $\Theta(n\log h)$, kde $h$ je počet bodov zostrojeného konvexného obalu.)

Začneme tým, že dané body usporiadame zľava doprava a v rámci rovnakej x-ovej súradnice zdola hore. Následne konvexný obal zostrojíme v dvoch prechodoch: v prvom jeho hornú a v druhom jeho dolnú "polovicu". Presnejšie, prvý bod aj posledný bod z usporiadaného poradia (t.j. najspodnejší z najľavejších a najhornejší z najpravejších) určite oba ležia na konvexnom obale a delia ho na dva úseky: "horný" a "dolný". V každom prechode zostrojíme jeden z nich.

Popíšeme prvý prechod, teda zostrojenie horného obalu. (Druhý prechod je potom takmer identický, až na znamienka.)

Budeme postupne spracúvať body v usporiadanom poradí, ktoré sme si pred chvíľou vyrobili. Po spracovaní každého bodu bude platiť, že práve poznáme horný konvexný obal doteraz spracovaných bodov. To je nejaká lomená čiara, ktorá začína v prvom spracovanom bode, niekoľkokrát (možno nulakrát) zatočí doprava a skončí v poslednom spracovanom bode.

Príklad takejto situácie:

Čo sa teraz stane, keď nám pribudne nasledujúci bod? Body spracúvame usporiadané, nasledujúci bod teda pribudne napravo od doterajšieho konca horného obalu. Najjednoduchšie čo môžeme teraz spraviť je jednoducho obal poň predĺžiť:

Občas nám však môže nastať práve taká situácia ako na našom obrázku: tým, že sme obal predĺžili, zrazu zatáča do nesprávnej strany a vznikla v ňom "preliačenina". Toto potrebujeme napraviť. Ako? Jednoducho. Problémy vždy nutne spôsobuje práve predposledný bod. Ten sa nachádza na našej lomenej čiare, v skutočnosti však už má ležať pod horným obalom. Z obalu ho preto vyhodíme:

Ale čo to? Aj nasledujúci bod (ktorý je teraz novým predposledným bodom) ešte robí problémy. Aj v ňom chce naša lomená čiara zatáčať doľava, a to nám jednoznačne hovorí, že aj tento bod patrí pod nový horný obal:

A už je všetko v poriadku a máme hotový horný obal novej množiny bodov.

Akú má toto riešenie časovú zložitosť? Na začiatku potrebujeme usporiadať $n$ bodov, čo spravíme v čase $\Theta(n\log n)$. Následne robíme dva prechody a pri každom vyššie popísaným spôsobom udržiavame časť konvexného obalu. Na prvý pohľad by sa mohlo zdať, že časová zložitosť každého prechodu je kvadratická ­— pri pridaní nového bodu môže byť treba veľa nových vyhodiť. Toto sa ale nemôže stávať často. Dobrý pohľad na časovú zložitosť je napr. nasledovný: každý bod na konvexný obal raz pridáme (keď ho spracúvame) a následne ho z obalu nanajvýš raz vyhodíme. Dokopy má celý prechod teda lineárnu časovú zložitosť. (Keďže vždy vyhadzujeme body len z konca zostrojovaného konvexného obalu, stačí si pri implementácii jeho vrcholy pamätať v zásobníku.)