V geometrických algoritmů je výpočet konvexního obalu je algoritmický problém . Skládá se, daný souborem bodů, z výpočtu jejich konvexní obálky .
Konvexní trup množiny bodů je nejmenší konvexní množina, která obsahuje všechny. Je to mnohostěn, jehož vrcholy jsou body množiny. Výpočet konvexní obálky spočívá ve výpočtu kompaktní reprezentace obálky, nejčastěji jejích vrcholů.
Toto je problém, který má mnoho aplikací, například v rozpoznávání vzorů, a který je ústředním bodem výpočetní geometrie .
Rovinný případ je případ, kdy jsou body uspořádány v rovině. Měříme složitost v čase jako funkci počtu bodů vstupu n a počtu bodů na obálce h . Pro tento případ existuje mnoho algoritmů.
Myšlenkou procházky Jarvis (nebo algoritmu dárkového balení ) je „zabalení“ sady bodů do „dárkového balení“: tento papír zavěsíme na jeden z bodů, roztáhneme jej a poté se otočíme kolem bodu mrak. Složitost algoritmu je O (nh) .
Kurz Graham (aka Graham skenování ), je najít místo nejmenšího osy x, třídit všechny ostatní body z úhlu dělají s ním (a osa x), pak zvážit trojice po sobě jdoucích bodů, určit, které z nich jsou v obálce. Jeho složitost spočívá v třídění , to znamená O (n.log (n)) .
Chan algoritmus , probíhá v několika fázích. Nejprve rozdělení bodů do několika skupin, poté výpočet konvexních obálek těchto skupin pomocí algoritmu v O (n.log (n)) (jako Grahamova procházka ) a nakonec Jarvisova procházka pomocí těchto již vypočtených obálek . Jeho složitost je v O (n.log (h)) .
Quickhull je algoritmus rozděl a panuj . Jeho průměrná složitost je O (n.log (n)). Jeho nejhorší složitost je O (n²).
Shamos ' Algoritmus je rozděl a panuj. Jeho složitost je O (n.log (n)).
Algoritmus Kirkpatrick a Seidel (v) má složitost O (n.log (h)) .
Existují i jiné algoritmy, například Andrewův algoritmus.
Preparata-Hong algoritmus pracuje pro rozměrech 2 a 3.
U dimenzí větších než 2 funguje algoritmus quickhull a Chanův algoritmus.
Existují také algoritmy pro aproximaci konvexní obálky.