I geometrisk algoritme er beregningen af den konvekse kuvert et algoritmisk problem . Den består, givet et sæt punkter, i beregningen af deres konvekse konvolut .
Det konvekse skrog af et sæt punkter er det mindste konvekse sæt, der indeholder dem alle. Det er en polyhedron, hvis hjørner er punkter i sættet. Beregningen af den konvekse konvolut består i beregning af en kompakt repræsentation af konvolutten, ofte hjørnerne deraf.
Dette er et problem, der har mange anvendelser, for eksempel i mønstergenkendelse, og som er centralt i beregningsgeometri .
Den plane sag er tilfældet, hvor punkterne er arrangeret i flyet. Vi måler kompleksiteten i tid som en funktion af antallet af punkter på input n og antallet af punkter på konvolutten h . Der er mange algoritmer til denne sag.
Ideen med Jarvis walk (eller gaveindpakningsalgoritmen ) er at "pakke" sæt af punkter i en "gaveindpakning": vi hænger dette papir på et af punkterne, vi strækker det, så vender vi rundt om punktet Sky. Kompleksiteten af algoritmen er O (nh) .
Den Kurset Graham (alias Graham scanning ) er at finde det punkt mindste x-aksen, sortere alle andre punkter fra den vinkel, de gør med det (og x-aksen), og derefter overveje de trillinger successive punkter, for at afgøre, hvilke af dem er i konvolutten. Dens kompleksitet er at sortere , det vil sige O (n.log (n)) .
Den Chan algoritmen , forløber i etaper. Først en opdeling af punkterne i flere grupper, derefter beregningen af de konvekse konvolutter for disse grupper med en algoritme i O (n.log (n)) (som Graham- gangen ) og til sidst en Jarvis-gang ved hjælp af disse allerede beregnede konvolutter . Dens kompleksitet er i O (n.log (h)) .
Quickhull er en kløft- og erobringsalgoritme . Dens gennemsnitlige kompleksitet er O (n.log (n)). Dens worst-case kompleksitet er O (n²).
Shamos ' algoritme er en delings- og erobringsalgoritme. Dens kompleksitet er O (n.log (n)).
Den algoritmen af Kirkpatrick og Seidel (i) har en kompleksitet på O (n.log (h)) .
Der findes andre algoritmer, som Andrews algoritme.
Den Preparata-Hong algoritme virker for dimensionerne 2 og 3.
For dimensioner større end 2 fungerer quickhull-algoritmen og Chan's algoritme.
Der er også algoritmer til at tilnærme den konvekse konvolut.