W geometrii algorytmicznego , quickhull jest algorytm do obliczania wypukłą kadłub . To algorytm dziel i rządź .
Zwróćmy uwagę, że wypukła obwiedni wyznaczonej E punktów określa się przez podzbiór F z E . Zasada działania algorytmu jest następująca. Najpierw znajdujemy skrajny lewy punkt P i prawy punkt Q (w przypadku równości wybieramy arbitralnie). Punkty P i Q należą do wypukłej obwiedni. Następnie możemy rozwiązać problem, znajdując wypukłą obwiednię punktów powyżej linii (PQ) i punktów poniżej linii, a następnie łącząc listy punktów (nie powtarzając P i Q ). Podproblemy mają wtedy bardziej ograniczoną postać niż pierwotne wystąpienie: mamy dwa punkty na linii, tak że wszystkie punkty znajdują się po tej samej stronie linii, powiedzmy po lewej stronie (PQ) , i wszystkie punkty, które należą do linii znajdują się w segmencie [PQ] . Następnie znajdujemy punkt H najbardziej oddalony od linii. Wypukłą obwiednię powyższych punktów (PQ) uzyskuje się następnie przez połączenie wypukłej obwiedni punktów na lewo od (PH) i punktów na lewo od (HQ) . Możemy rekurencyjnie obliczyć te zbiory (są w tej samej konfiguracji co poprzednio).
Algorytm ma ten sam typ złożoności czasowej , co algorytm sortowania quicksort , w najgorszym przypadku i średnio .
Algorytm pojawia się w książce Computational Geometry - An Introduction w 1985 roku, w której autorzy przypisują pomysły kilku artykułom z lat 70.