Rozważmy ogólny przypadek, gdy wejściem do algorytmu jest skończony nieuporządkowany zbiór punktów na płaszczyźnie kartezjańskiej. Ważny przypadek szczególny, w którym punkty są podane w kolejności przechodzenia przez granicę wielokąta prostego, jest opisany później w osobnym podrozdziale.
Jeśli nie wszystkie punkty leżą na tej samej prostej, to ich kadłub wypukły jest wielokątem wypukłym, którego wierzchołkami są niektóre z punktów zbioru wejściowego. Jego najczęstszą reprezentacją jest lista jego wierzchołków uporządkowanych wzdłuż jego granicy zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara. W niektórych zastosowaniach wygodnie jest reprezentować wielokąt wypukły jako przecięcie zbioru półpłaszczyzn.
Dolna granica złożoności obliczeniowejEdit
Dla skończonego zbioru punktów na płaszczyźnie dolna granica złożoności obliczeniowej znajdowania kadłuba wypukłego reprezentowanego jako wielokąt wypukły jest łatwa do pokazania, że jest taka sama jak dla sortowania przy użyciu następującej redukcji. Dla zbioru x 1 , … , x n {{displaystyle x_{1}},∗ ,x_{n}}
liczb do sortowania rozważ zbiór punktów ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {displaystyle (x_{1},x_{1}^{2}),↓,x_{n},x_{n}^{2})}
punktów na płaszczyźnie. Ponieważ leżą one na paraboli, która jest krzywą wypukłą, łatwo zauważyć, że wierzchołki kadłuba wypukłego, po przejściu wzdłuż granicy, dają posortowaną kolejność liczb x 1 , … , x n {{displaystyle x_{1}},\dots ,x_{n}}
. Najwyraźniej do opisanej transformacji liczb na punkty, a następnie wyodrębnienia ich posortowanej kolejności, potrzebny jest czas liniowy. Dlatego w ogólnym przypadku nie da się obliczyć wypukłego kadłuba n punktów szybciej niż sortowanie.
Standardowy dolny limit Ω(n log n) dla sortowania jest udowodniony w modelu drzewa decyzyjnego, w którym można wykonywać tylko porównania numeryczne, a nie operacje arytmetyczne; jednak w tym modelu nie można w ogóle obliczać kadłubów wypukłych. Sortowanie wymaga również czasu Ω(n log n) w algebraicznym modelu drzewa decyzyjnego, który jest bardziej odpowiedni dla kadłubów wypukłych, a w tym modelu kadłuby wypukłe również wymagają czasu Ω(n log n). Jednak w modelach arytmetyki komputerowej, które pozwalają na sortowanie liczb szybciej niż O(n log n) czas, na przykład za pomocą algorytmów sortowania liczb całkowitych, planarne kadłuby wypukłe mogą być również obliczane szybciej: algorytm skanowania Grahama dla kadłubów wypukłych składa się z pojedynczego kroku sortowania, po którym następuje liniowa ilość dodatkowej pracy.
Optymalne algorytmy wrażliwe na wielkość danych wyjściowychEdit
Jak stwierdzono powyżej, złożoność znajdowania kadłuba wypukłego w funkcji rozmiaru danych wejściowych n jest dolnie ograniczona przez Ω(n log n). Jednakże, złożoność niektórych algorytmów znajdowania wypukłego kadłuba może być scharakteryzowana zarówno w kategoriach rozmiaru wejściowego n, jak i rozmiaru wyjściowego h (liczby punktów w kadłubie). Takie algorytmy są nazywane algorytmami wrażliwymi na wielkość wyjściową. Mogą one być asymptotycznie wydajniejsze od algorytmów Θ(n log n) w przypadkach, gdy h = o(n).
Dolna granica najgorszego czasu działania algorytmów output-sensitive convex hull została wyznaczona na Ω(n log h) w przypadku planarnym. Istnieje kilka algorytmów, które osiągają tę optymalną złożoność czasową. Najwcześniejszy z nich został wprowadzony przez Kirkpatricka i Seidla w 1986 roku (którzy nazwali go „the ultimate convex hull algorithm”). Znacznie prostszy algorytm został opracowany przez Chan w 1996 roku i jest nazywany algorytmem Chan’a.
AlgorytmyEdit
Znane algorytmy kadłuba wypukłego są wymienione poniżej, uporządkowane według daty pierwszej publikacji. Złożoność czasowa każdego algorytmu jest podana w kategoriach liczby punktów wejściowych n i liczby punktów na kadłubie h. Zauważ, że w najgorszym przypadku h może być tak duże jak n.
- Gift wrapping, a.k.a. Jarvis march – O(nh)
Jeden z najprostszych (choć nie najbardziej efektywnych czasowo w najgorszym przypadku) algorytmów planarnych. Stworzony niezależnie przez Chanda & Kapura w 1970 i R. A. Jarvisa w 1973. Ma on złożoność czasową O(nh), gdzie n jest liczbą punktów w zbiorze, a h jest liczbą punktów w kadłubie. W najgorszym przypadku złożoność wynosi Θ(n2). - Graham scan – O(n log n)
Nieco bardziej wyrafinowany, ale znacznie wydajniejszy algorytm, opublikowany przez Ronalda Grahama w 1972 roku. Jeśli punkty są już posortowane po jednej ze współrzędnych lub po kącie względem ustalonego wektora, to algorytm zajmuje O(n) czasu. - Quickhull
Wytworzony niezależnie w 1977 roku przez W. Eddy’ego i w 1978 roku przez A. Bykata. Podobnie jak algorytm quicksort, ma on oczekiwaną złożoność czasową O(n log n), ale w najgorszym przypadku może zdegenerować się do O(n2). - Divide and conquer – O(n log n)
Kolejny algorytm O(n log n), opublikowany w 1977 roku przez Preparata i Honga. Algorytm ten ma również zastosowanie w przypadku trójwymiarowym. - Monotoniczny łańcuch, a.k.a. Andrew’s algorithm- O(n log n)
Opublikowany w 1979 roku przez A. M. Andrew. Algorytm ten może być postrzegany jako wariant skanowania Grahama, który sortuje punkty leksykograficznie według ich współrzędnych. Gdy dane wejściowe są już posortowane, algorytm zajmuje O(n) czasu. - Incremental convex hull algorithm – O(n log n)
Opublikowany w 1984 r. przez Michaela Kallaya. - Kirkpatrick-Seidel algorithm – O(n log h)
Pierwszy optymalny algorytm wrażliwy na wynik. Modyfikuje algorytm dziel i zwyciężaj poprzez zastosowanie techniki marriage-before-conquest i niskowymiarowego programowania liniowego. Opublikowany przez Kirkpatricka i Seidla w 1986 roku. - Algorytm Chana – O(n log h)
Prostszy optymalny algorytm wrażliwy na wyjście stworzony przez Chana w 1996 roku. Łączy on pakowanie prezentów z wykonaniem algorytmu O(n log n) (takiego jak Graham scan) na małych podzbiorach danych wejściowych.
Heurystyka Akl-ToussaintEdit
Następująca prosta heurystyka jest często używana jako pierwszy krok w implementacjach algorytmów kadłuba wypukłego w celu poprawy ich wydajności. Jest on oparty na wydajnym algorytmie kadłuba wypukłego autorstwa Selima Arkla i G. T. Toussainta z 1978 roku. Idea polega na szybkim wykluczeniu wielu punktów, które i tak nie byłyby częścią kadłuba wypukłego. Metoda ta opiera się na następującym pomyśle. Znajdź dwa punkty o najmniejszej i największej współrzędnej x, oraz dwa punkty o najmniejszej i największej współrzędnej y. (Każda z tych operacji zajmuje O(n).) Te cztery punkty tworzą wypukły czworokąt, a wszystkie punkty, które leżą w tym czworokącie (z wyjątkiem czterech początkowo wybranych wierzchołków) nie są częścią wypukłego kadłuba. Znalezienie wszystkich tych punktów, które leżą w tym czworokącie jest również O(n), a zatem cała operacja jest O(n). Opcjonalnie, punkty o najmniejszych i największych sumach współrzędnych x i y oraz o najmniejszych i największych różnicach współrzędnych x i y mogą również zostać dodane do czworokąta, tworząc w ten sposób nieregularny ośmiokąt wypukły, którego wnętrza można bezpiecznie wyrzucić. Jeśli punkty są zmiennymi losowymi, to dla wąskiej, ale powszechnie spotykanej klasy funkcji gęstości prawdopodobieństwa, ten wyrzucony krok wstępnego przetwarzania sprawi, że algorytm kadłuba wypukłego będzie działał w liniowym oczekiwanym czasie, nawet jeśli złożoność algorytmu kadłuba wypukłego w najgorszym przypadku jest kwadratowa w n.
On-line i dynamiczne problemy kadłuba wypukłegoEdit
Dyskusja powyżej rozważa przypadek, gdy wszystkie punkty wejściowe są znane z góry. Można rozważyć dwa inne ustawienia.
- Online convex hull problem: Punkty wejściowe są uzyskiwane sekwencyjnie jeden po drugim. Po pojawieniu się każdego punktu na wejściu, należy sprawnie obliczyć kadłub wypukły dla uzyskanego do tej pory zbioru punktów.
- Dynamiczne utrzymywanie kadłuba wypukłego: Punkty wejściowe mogą być sekwencyjnie wstawiane lub usuwane, a kadłub wypukły musi być aktualizowany po każdej operacji wstawienia/usunięcia.
Wstawienie punktu może zwiększyć liczbę wierzchołków kadłuba wypukłego co najwyżej o 1, natomiast usunięcie może przekształcić n-werteksowy kadłub wypukły w n-1-werteksowy.
Wersja online może być obsługiwana z O(log n) na punkt, co jest asymptotycznie optymalne. Wersja dynamiczna może być obsługiwana z O(log2 n) na operację.
Prosty wielokątEdit
Wypukły kadłub prostego wielokąta jest podzielony przez wielokąt na kawałki, z których jeden jest samym wielokątem, a pozostałe są kieszeniami ograniczonymi przez kawałek granicy wielokąta i pojedynczą krawędź kadłuba. Chociaż opublikowano wiele algorytmów dla problemu konstruowania wypukłego kadłuba prostego wielokąta, prawie połowa z nich jest niepoprawna.McCallum i Avis dostarczyli pierwszy poprawny algorytm.Późniejsze uproszczenie autorstwa Grahama & Yao (1983) i Lee (1983) wykorzystuje tylko pojedynczą strukturę danych stosu. Ich algorytm przemierza wielokąt zgodnie z ruchem wskazówek zegara, zaczynając od jego najbardziej lewego wierzchołka. Na stosie przechowuje wypukłą sekwencję wierzchołków, które nie zostały jeszcze zidentyfikowane jako należące do kieszeni. W każdym kroku algorytm podąża ścieżką wzdłuż wielokąta od wierzchołka stosu do następnego wierzchołka, który nie znajduje się w jednej z dwóch kieszeni przylegających do wierzchołka stosu. Następnie, podczas gdy dwa wierzchołki na stosie wraz z tym nowym wierzchołkiem nie są w pozycji wypukłej, algorytm odbija stos, zanim ostatecznie wepchnie nowy wierzchołek na stos. Gdy traversal zgodnie z ruchem wskazówek zegara osiągnie punkt początkowy, algorytm zwraca sekwencję wierzchołków stosu jako kadłub.