I algoritmisk geometri er quickhull en algoritme for beregning av det konvekse skroget . Det er en splitt-og-erobre algoritme .
Legg merke til først at den konvekse konvolutten av et sett E av punkter er avgrenset av et undersett F av E . Prinsippet for algoritmen er som følger. Først finner vi det venstre punktet P og det høyre punktet Q (i tilfelle likhet velger vi vilkårlig). Punktene P og Q tilhører den konvekse konvolutten. Vi kan deretter løse problemet ved å finne den konvekse konvolutten til punktene over linjen (PQ) og punktene under linjen, deretter ved å sammenkoble punktlistene (ved ikke å gjenta P og Q ). Delproblemene har da en mer begrenset form enn den opprinnelige forekomsten: vi har to punkter på en linje, slik at alle punktene er på samme side av linjen, si til venstre for (PQ) , og alle punktene som hører til til linjen er i segmentet [PQ] . Vi finner da punktet H lengst fra linjen. Den konvekse konvolutten til punktene ovenfor (PQ) oppnås deretter ved å sammenkoble den konvekse konvolutten til punktene til venstre for (PH) og den til punktene til venstre for (HQ) . Vi kan rekursivt beregne disse settene (de har samme konfigurasjon som før).
Algoritmen har samme type tidskompleksitet som sorteringsalgoritmen quicksort er å si, i verste fall og gjennomsnitt .
Algoritmen vises i boken Computational Geometry - An Introduction in 1985, der forfatterne tilskriver ideene til flere artikler fra 1970-tallet.