Algorytmy kadłuba wypukłego

Algorytmy konstruujące wypukłe otoczki różnych obiektów mają szerokie zastosowanie w matematyce i informatyce .

W geometrii obliczeniowej proponuje się liczne algorytmy obliczania wypukłej otoczki skończonego zbioru punktów, o różnej złożoności obliczeniowej .

Obliczenie otoczki wypukłej oznacza, że konstruowana jest jednoznaczna i wydajna reprezentacja wymaganego kształtu wypukłego. Złożoność odpowiednich algorytmów jest zwykle szacowana na podstawie n , liczby punktów wejściowych, a czasami także pod względem h , liczby punktów na wypukłym kadłubie.

Planarny przypadek

Rozważmy ogólny przypadek, gdy danymi wejściowymi 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ę prostego wielokąta, zostanie opisany w osobnym podrozdziale.

Jeśli nie wszystkie punkty leżą na tej samej linii, to ich wypukła powłoka jest wypukłym wielokątem , którego wierzchołki są niektórymi punktami w zbiorze wejściowym. Jego najczęstszą reprezentacją jest lista wierzchołków uporządkowanych wzdłuż granicy zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara. W niektórych zastosowaniach wygodnie jest przedstawić wypukły wielokąt jako przecięcie zestawu półpłaszczyzn .

Dolna granica złożoności obliczeniowej

Dla skończonego zestawu punktów na płaszczyźnie dolna granica złożoności obliczeniowej znajdowania wypukłej otoczki reprezentowanej jako wielokąt wypukły jest łatwo pokazana jako taka sama jak dla sortowania przy użyciu następującej redukcji . Dla zestawu ${\ Displaystyle x_ {1}, \ kropki, x_ {n}}$ zestaw ${\ Displaystyle (x_ {1}, x_ {1} ^ {2}), \ kropki, (x_ {n}, x_ {n} ^ {2})}$ punktów na płaszczyźnie. Ponieważ leżą na paraboli , która jest krzywą wypukłą , łatwo zauważyć, że wierzchołki wypukłej otoczki po przejściu wzdłuż granicy tworzą posortowany porządek liczb ${\ displaystyle x_ { 1},\kropki ,x_{n}}$ . Oczywiście do opisanego przekształcenia liczb na punkty, a następnie wyodrębnienia ich uporządkowanego porządku potrzebny jest czas liniowy . Dlatego w ogólnym przypadku wypukły kadłub n punktów nie może być obliczony szybciej niż sortowanie.

Standardowa dolna granica Ω ( n log n ) dla sortowania jest udowodniona w modelu drzewa decyzyjnego obliczeń, w którym można wykonywać tylko porównania numeryczne, ale nie operacje arytmetyczne; jednak w tym modelu w ogóle nie można obliczyć wypukłych kadłubów. Sortowanie wymaga również czasu Ω ( n log n ) w algebraicznym drzewie decyzyjnym modelu obliczeń, modelu, który jest bardziej odpowiedni dla wypukłych kadłubów, aw tym modelu wypukłe kadłuby również wymagają czasu Ω ( n log n ). Jednak w modelach arytmetyki komputerowej, które pozwalają na sortowanie liczb szybciej niż w czasie O ( n log n ), na przykład przy użyciu algorytmów sortowania liczb całkowitych , płaskie wypukłe łuski można również obliczyć szybciej: algorytm skanowania Grahama dla łusek wypukłych składa się pojedynczego etapu sortowania, po którym następuje liniowa ilość dodatkowej pracy.

Optymalne algorytmy wrażliwe na dane wyjściowe

Jak stwierdzono powyżej, złożoność znalezienia wypukłej otoczki jako funkcji wielkości wejściowej n jest dolna ograniczona przez Ω ( n log n ). Jednak złożoność niektórych algorytmów wypukłych kadłubów można scharakteryzować zarówno pod względem rozmiaru wejściowego n , jak i wyjściowego rozmiaru h (liczba punktów w kadłubie). Takie algorytmy nazywane są algorytmami wrażliwymi na dane wyjściowe . Mogą być asymptotycznie bardziej wydajne niż algorytmy Θ( n log n ) w przypadkach, gdy h = o ( n ).

Ustalono, że dolna granica czasu działania algorytmów wypukłego kadłuba w najgorszym przypadku wynosi Ω ( n log h ) w przypadku planarnym. Istnieje kilka algorytmów, które osiągają tę optymalną złożoność czasową . Najwcześniejszy został wprowadzony przez Kirkpatricka i Seidela w 1986 roku (którzy nazwali go „ algorytmem ostatecznego wypukłego kadłuba ”). Znacznie prostszy algorytm został opracowany przez Chana w 1996 roku i nosi nazwę algorytmu Chana .

Algorytmy

Znane algorytmy kadłuba wypukłego wymieniono poniżej, uporządkowane według daty pierwszej publikacji. Złożoność czasowa każdego algorytmu wyrażona jest liczbą punktów wejściowych n oraz liczbą punktów na kadłubie h . Zauważ, że w najgorszym przypadku h może być tak duże jak n .

Pakowanie prezentów , inaczej Jarvis march — O ( nh ) Jeden z najprostszych (choć w najgorszym przypadku nie najbardziej efektywny czasowo) algorytmów planarnych. Stworzony niezależnie przez Chanda i Kapura w 1970 r. i RA Jarvisa w 1973 r. Ma złożoność czasową O ( nh ) , gdzie n to liczba punktów w zbiorze, a h to liczba punktów w kadłubie. W najgorszym przypadku złożoność wynosi Θ ( n ² ).
Skan Grahama — O ( n log n ) Nieco bardziej wyrafinowany, ale znacznie wydajniejszy algorytm, opublikowany przez Ronalda Grahama w 1972 r. Jeśli punkty są już posortowane według jednej ze współrzędnych lub kąta do ustalonego wektora, wówczas algorytm zajmuje O( n ) czasu.
Quickhull Utworzony niezależnie w 1977 przez W. Eddy'ego iw 1978 przez A. Bykata. Podobnie jak szybkiego sortowania , ma oczekiwaną złożoność czasową O ( n log n ), ale w najgorszym przypadku może ulec degeneracji do O ( n ^{2 ).}
Dziel i rządź — O ( n log n ) Kolejny algorytm O ( n log n ), opublikowany w 1977 r. przez Preparatę i Honga. Algorytm ten ma również zastosowanie do przypadku trójwymiarowego.
Łańcuch monotoniczny , inaczej algorytm Andrew — O ( n log n ) Opublikowany w 1979 r. przez AM Andrew. Algorytm można postrzegać 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.
Algorytm przyrostowego wypukłego kadłuba — O ( n log n ) Opublikowany w 1984 r. przez Michaela Kallaya.
Algorytm Kirkpatricka – Seidela — O ( n log h ) Pierwszy optymalny algorytm wrażliwy na wyjście. Modyfikuje algorytm dziel i zwyciężaj, wykorzystując technikę małżeństwa przed podbojem i niskowymiarowego programowania liniowego . Opublikowane przez Kirkpatricka i Seidela w 1986 roku.
Algorytm Chana — O ( n log h ) Prostszy algorytm optymalnie wrażliwy na dane wyjściowe, stworzony przez Chana w 1996 r. Łączy pakowanie prezentów z wykonaniem algorytmu O ( n log n ) (takiego jak skanowanie Grahama) na małych podzbiorach danych wejściowych .

Heurystyka Akla-Toussainta

Poniższa prosta heurystyka jest często używana jako pierwszy krok w implementacji algorytmów wypukłych kadłubów w celu poprawy ich wydajności. Opiera się na efektywnym algorytmie wypukłego kadłuba Selima Akla i GT Toussaint , 1978. Chodzi o to, aby szybko wykluczyć wiele punktów, które i tak nie byłyby częścią wypukłego kadłuba. Ta metoda opiera się na następującym pomyśle. Znajdź dwa punkty o najniższych i najwyższych współrzędnych x oraz dwa punkty o najniższych i najwyższych współrzędnych y. (Każda z tych operacji trwa O ( n ).) Te cztery punkty tworzą wypukły czworobok , a wszystkie punkty leżące w tym czworoboku (z wyjątkiem czterech początkowo wybranych wierzchołków) nie są częścią wypukłej otoczki. Znalezienie wszystkich tych punktów leżących w tym czworokącie to także O( n ), a zatem cała operacja to O( n ). Opcjonalnie do czworoboku można dodać 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, tworząc w ten sposób nieregularny wypukły ośmiokąt, którego wnętrza mogą bezpiecznie wyrzucić. Jeśli punkty są zmiennymi losowymi, to dla wąskiej, ale powszechnie spotykanej klasy funkcji gęstości prawdopodobieństwa, ten odrzucany krok przetwarzania wstępnego spowoduje, że algorytm kadłuba wypukłego będzie działał w oczekiwanym czasie liniowym, nawet jeśli najgorszy przypadek złożoności wypukłej algorytm kadłuba jest kwadratowy w n .

On-line i dynamiczne wypukłe problemy kadłuba

W powyższym omówieniu rozważany jest przypadek, gdy wszystkie punkty wejściowe są znane z góry. Można rozważyć dwa inne ustawienia.

Online wypukły problem kadłuba : Punkty wejściowe są uzyskiwane sekwencyjnie jeden po drugim. Po tym, jak każdy punkt pojawi się na wejściu, wypukły kadłub dla dotychczas uzyskanego zestawu punktów musi zostać skutecznie obliczony.
konserwacja 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 wstawiania/usuwania.

Wstawienie punktu może zwiększyć liczbę wierzchołków otoczki wypukłej co najwyżej o 1, natomiast usunięcie może przekształcić otoczkę wypukłą o n -wierzchołkach w otoczkę o n-1 wierzchołkach.

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(log ² n ) na operację.

Prosty wielokąt

Wypukły kadłub prostego wielokąta jest podzielony przez wielokąt na części, z których jedna jest samym wielokątem, a pozostałe to kieszenie ograniczone fragmentem granicy wielokąta i pojedynczą krawędzią kadłuba. Chociaż opublikowano wiele algorytmów dotyczących problemu konstruowania wypukłej otoczki prostego wielokąta, prawie połowa z nich jest błędna. McCallum i Avis dostarczyli pierwszy poprawny algorytm. Późniejsze uproszczenie Grahama i Yao (1983) oraz Lee (1983) używa tylko struktury danych z jednym stosem . Ich algorytm przemierza wielokąt zgodnie z ruchem wskazówek zegara, zaczynając od jego lewego wierzchołka. W ten sposób przechowuje wypukłą sekwencję wierzchołków na stosie, tych, które nie zostały jeszcze zidentyfikowane jako znajdujące się w kieszeniach. 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 górne wierzchołki na stosie wraz z tym nowym wierzchołkiem nie są w pozycji wypukłej, zdejmuje stos, zanim ostatecznie wepchnie nowy wierzchołek na stos. Gdy przejście zgodnie z ruchem wskazówek zegara osiągnie punkt początkowy, algorytm zwraca sekwencję wierzchołków stosu jako kadłub.

Wyższe wymiary

Znanych jest wiele algorytmów dla przypadku trójwymiarowego, a także dla dowolnych wymiarów. Algorytm Chana jest używany dla wymiarów 2 i 3, a Quickhull jest używany do obliczania wypukłej powłoki w wyższych wymiarach.

W przypadku skończonego zbioru punktów wypukła powłoka jest wypukłym wielościanem w trzech wymiarach lub ogólnie wypukłym polytopem dla dowolnej liczby wymiarów, którego wierzchołki są niektórymi punktami w zbiorze wejściowym. Jego reprezentacja nie jest jednak tak prosta jak w przypadku planarnym. W wyższych wymiarach, nawet jeśli znane są wierzchołki wypukłego polytopu, konstrukcja jego ścian jest zadaniem nietrywialnym, podobnie jak podwójny problem konstruowania wierzchołków przy danych ścianach. Rozmiar informacji o powierzchni wyjściowej może być wykładniczo większy niż rozmiar wierzchołków wejściowych, a nawet w przypadkach, gdy dane wejściowe i wyjściowe mają porównywalny rozmiar, znane algorytmy dla wielowymiarowych wypukłych powłok nie są wrażliwe na dane wyjściowe z powodu zarówno problemy ze zdegenerowanymi danymi wejściowymi i wynikami pośrednimi o dużej złożoności.

Zobacz też

Kadłub wypukły ortogonalny

Dalsza lektura

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sekcja 33.3: Znajdowanie wypukłej otoczki, s. 947–957.
Franco P. Preparata , SJ Hong. Wypukłe kadłuby skończonych zbiorów punktów w dwóch i trzech wymiarach , komun. ACM, tom. 20, nie. 2, s. 87–93, 1977.
Marka de Berga ; Marca van Krevelda ; Marka Overmarsa i Otfrieda Schwarzkopfa (2000). Geometria obliczeniowa (wydanie drugie poprawione). Springer-Verlag . ISBN 978-3-540-65620-3 . Sekcja 1.1: Przykład: łuski wypukłe (opisano klasyczne algorytmy dla 2-wymiarowych łusek wypukłych). Rozdział 11: Convex Hulls: s. 235–250 (opisuje losowy algorytm dla trójwymiarowych wypukłych kadłubów dzięki Clarksonowi i Shorowi).

Linki zewnętrzne

Weisstein, Eric W. „Wypukły kadłub” . MathWorld .
Kadłub wypukły 2D, 3D i dD w CGAL , bibliotece algorytmów geometrii obliczeniowej
Kod Qhulla dla wypukłego kadłuba, triangulacji Delaunaya, diagramu Woronoja i przecięcia półprzestrzeni
Demo jako algorytmy Flash swf , Jarvis, Graham, Quick (dziel i zwyciężaj) i Chan
Algorytm pakowania prezentów w C#