Konvexný obal

Pre ľubovoľnú konečnú množinu bodov v rovine je jednoznačne určený útvar s najmenším obvodom, ktorý ich všetky obsahuje. Je ním ich konvexný obal. (Dôkaz tohto tvrdenia uvádzame nižšie.)

Čo je to konvexný obal?

Útvar $\cal U$ v rovine voláme konvexný, ak má nasledovnú vlastnosť: pre ľubovoľné dva body $A,B\in\cal U$ aj celá úsečka $AB$ patrí do útvaru $\cal U$. Ľudovo povedané, konvexný útvar nemá žiadne diery ani záhyby dovnútra.

Prienik ľubovoľného (dokonca aj nespočítateľne nekonečného!) množstva konvexných útvarov je zjavne opäť konvexný útvar. (Totiž nech $A,B$ sú ľubovoľné dva body z toho prieniku. Potom tieto body sú v každom z pôvodných útvarov. A keďže všetky tie útvary sú konvexné, každý obsahuje celú úsečku $AB$. A teda táto úsečka patrí aj do ich prieniku.)

Konvexný obal danej množiny bodov teda môžeme formálne definovať ako prienik úplne všetkých konvexných útvarov, ktoré danú množinu bodov obsahujú. Menej formálne ale omnoho názornejšie je povedať, že konvexný obal danej množiny bodov je najmenší zo všetkých konvexných útvarov, ktoré danú množinu obsahujú.

A nie je ťažké si uvedomiť, ako tento konvexný obal vyzerá: konvexným obalom danej konečnej množiny bodov v rovine je vždy mnohouholník, ktorého vrcholmi sú niektoré spomedzi zadaných bodov. (Spolu s danými bodmi musí konvexný obal obsahovať aj všetky úsečky spájajúce dva z daných bodov. Tie z úsečiek, ktoré ležia "na obvode", tvoria hranicu hľadaného konvexného mnohouholníka.)

A prečo má teda práve konvexný obal zo všetkých možných útvarov, ktoré našu množinu bodov obsahujú, najmenší obvod?

Intuitívne, predstavme si naše body ako klince a hľadaný útvar ako gumičku natiahnutú okolo nich. Keď gumičku pustíme, tá sa začne sťahovať (a teda skracovať). Najradšej by sa celá skrátila na nulovú dĺžku, to jej ale nedovolia klince v jej vnútri. Časom sa teda ustáli v polohe kedy je najkratšia ako sa dá ­— bude napnutá okolo všetkých "vonkajších" klincov. Inými slovami, bude tvoriť práve obvod vyššie popísaného konvexného obalu.

Formálny matematický dôkaz by sa dal spraviť napr. sporom. Nech teda existuje útvar $\cal U$, ktorý obsahuje všetky dané body a má menší obvod ako ich konvexný obal. Zoberme ľubovoľnú stranu $AB$ konvexného obalu, ktorá nie je (celá) súčasťou obvodu útvaru $\cal U$. Predĺžme $AB$ na priamku a označme $A'$ a $B'$ "najľavejší" a "najpravejší" z bodov tejto priamky, ktoré ešte patria do útvaru $\cal U$. (Tieto body vždy existujú, lebo $A$ a $B$ patria do $\cal U$.) Ak ale teraz zahodíme časť obvodu $\cal U$ medzi $A'$ a $B'$ a nahradíme jú úsečkou $A'B'$, dostaneme nový útvar, ktorý tiež obsahuje všetky dané body a má obvod ostro kratší ako $\cal U$. A to je hľadaný spor.