W algorytmów geometrycznych The obliczeniowy obwiedni wypukłej jest algorytmiczne problemem . Polega ona na obliczeniu ich wypukłej obwiedni , biorąc pod uwagę zestaw punktów .
Wypukła część zbioru punktów jest najmniejszym zbiorem wypukłym, który zawiera je wszystkie. Jest to wielościan, którego wierzchołki są punktami zbioru. Obliczenie obwiedni wypukłej polega na obliczeniu zwartej reprezentacji obwiedni, najczęściej jej wierzchołków.
Jest to problem, który ma wiele zastosowań, na przykład w rozpoznawaniu wzorców, i który ma zasadnicze znaczenie dla geometrii obliczeniowej .
Przypadek planarny to przypadek, w którym punkty są rozmieszczone na płaszczyźnie. Złożoność w czasie jest mierzona jako funkcja liczby punktów wejścia n i liczby punktów na obwiedni h . Istnieje wiele algorytmów dla tego przypadku.
Idea spaceru Jarvisa (lub algorytmu pakowania prezentów ) polega na „zawinięciu” zestawu punktów w „opakowanie na prezent”: wieszamy ten papier w jednym z punktów, rozciągamy go, a następnie obracamy wokół punktu Chmura. Złożoność algorytmu wynosi O (nh) .
Oczywiście Graham (aka Algorytm Grahama ) jest znalezienie punktu najmniejszego osi x, sortować wszystkie inne punkty z kąta robią z niego (a oś x), a następnie rozważyć Trio z kolejnych punktów, aby ustalić, które z nich są w kopercie. Jego złożoność polega na sortowaniu , to znaczy O (n.log (n)) .
Algorytm Chan , przebiega w kilku etapach. Najpierw podzielenie punktów na kilka grup, następnie obliczenie wypukłych obwiedni tych grup za pomocą algorytmu w O (n.log (n)) (jak spacer Grahama ), a na koniec spacer Jarvisa przy użyciu tych już obliczonych obwiedni . Jego złożoność jest w O (n.log (h)) .
Quickhull to algorytm dziel i zwyciężaj . Jego średnia złożoność wynosi O (n.log (n)). Jego najgorsza złożoność wynosi O (n²).
Algorytm Shamosa to algorytm dziel i zwyciężaj. Jego złożoność to O (n.log (n)).
Algorytm Kirkpatrick i Seidel (w) ma złożoność O (n.log (H)) .
Istnieją inne algorytmy, takie jak algorytm Andrew.
Algorytm Preparata-Hong pracuje wymiarach 2 i 3.
Dla wymiarów większych niż 2 działa algorytm quickhull i algorytm Chana.
Istnieją również algorytmy przybliżające wypukły kadłub.