Konvexný obal

V matematike je konvexný obal množiny bodov X na Euklidovskej ploche alebo v Euklidovskom priestore definovaný, ako najmenšia konvexná množina obsahujúca množinu X.

Konvexný obal červenej množiny je modrá množina

Definícia

Ilustrácia nekonvexnej množiny bodov. Keďže červená čast úsečky spájajúcej body X a Y je mimo množiny (zelená), daná množina je nekonvexná.

Množina bodov je definovaná ako konvexná ak v sebe obsahuje všetky úsečky spájajúce každú dvojicu bodov danej množiny.

Formálne je konvexný obal definovaný ako prienik všetkých konvexných množín obsahujúcich X, alebo ako množina všetkých konvexných kombinácii bodov v X.

Konvexný obal konečnej množiny: analógia s gumičkou

Ako konvexný obal vyzerá si môžeme predstaviť pomocou myšlienkového experimentu. Predstavme si, že X je ohraničená množina bodov na ploche. Ďalej si predstavme každý jej bod ako klinec trčiaci z podlahy. Zoberme elastickú gumičku a natiahnime ju tak aby vnútri nej boli všetky klince. Keď teraz pustíme gumičku, stiahne sa aby minimalizovala svoj obvod a natesno pritom obkolesí všetky klince. Plocha ohraničená touto gumičkou bude konvexný obal množiny bodov X.

Výpočet konvexného obalu

Príklad konvexného obalu bodov na ploche

Algoritmický problém hľadania konvexného obalu konečnej množiny bodov v Euklidovských priestoroch je jedným z fundamentálnych problémov geometrie v informatike.

Poznáme množstvo algoritmov na výpočet konvexného obalu konečného počtu bodov alebo rôznych iných geometrických tvarov.

Výpočet konvexného obalu obnáša zostrojenie jednoznačnej a efektívnej reprezentácie požadovaného konvexného útvaru.

Zložitosť jednotlivých algoritmov je zvyčajne odhadovaná v závislosti od $n$, čiže počtu vstupných bodov, a $h$, čiže počtu výstupných bodov, tj. počet bodov tvoriacich konvexný obal.

Pre body v 2D a 3D existujú algoritmy pracujúce s časovou zložitosťou $O(n\log h)$. Pre dimenzie $d>3$ poznáme algoritmy, ktorých časová zložitosť je rovná $O(n^{\lfloor d/2\rfloor })$, co je zároveň aj optimálne riešenie tohoto problému.

Využitie

3D konvexný obal

Problém nájdenia konvexných obalov má praktické využitie napríklad v rozpoznávaní vzorov, spracovaní obrazu, štatistikách, geografickom informačnom systéme, teórii hier, konštrukcii fázových diagramov a statickej analýze kódu pomocou abstraktnej interpretácie. Slúži tiež ako nástroj, stavebný blok, pre množstvo ďalších výpočtovo-geometrických algoritmov.

Konvexný obal je bežne známy ako Minimal Convex Polygon (MCP) v etiológii, kde je klasický, hoci možno zjednodušujúci, prístup pri odhadovaní rozsahu teritória zvieraťa na základe bodov, v ktorých bolo zviera pozorované. Extrémne hodnoty môžu spôsobiť, že MCP je nadbytočne veľký, a preto sa často používajú voľnejšie prístupy, ktoré obsahujú len podmnožinu pozorovaní (napr. nájsť MCP, ktorý obsahuje aspoň 95% bodov).