Wypukły kadłub prostego wielokąta
W geometrii dyskretnej i geometrii obliczeniowej wypukła powłoka prostego wielokąta jest wielokątem o minimalnym obwodzie, który zawiera dany prosty wielokąt . Jest to szczególny przypadek bardziej ogólnej koncepcji kadłuba wypukłego . Można go obliczyć w czasie liniowym , szybciej niż algorytmy dla wypukłych powłok zbiorów punktowych .
Wypukłą otoczkę wielokąta prostego można podzielić na sam dany wielokąt oraz na kieszenie wielokątne ograniczone wielokątnym łańcuchem wielokąta wraz z pojedynczą wypukłą krawędzią otoczki. Wielokrotne odbijanie arbitralnie wybranej kieszeni w poprzek tej wypukłej krawędzi kadłuba tworzy sekwencję większych prostych wielokątów; zgodnie z twierdzeniem Erdősa – Nagya proces ten ostatecznie kończy się wypukłym wielokątem.
Struktura
Wypukły kadłub prostego wielokąta sam jest wypukłym wielokątem . Nałożenie oryginalnego prostego wielokąta na jego wypukły kadłub dzieli ten wypukły wielokąt na regiony, z których jeden jest oryginalnym wielokątem. Pozostałe regiony nazywane są kieszeniami . Każda kieszeń jest sama w sobie prostym wielokątem, ograniczonym wielokątnym łańcuchem na granicy danego prostego wielokąta i pojedynczą krawędzią wypukłej otoczki. Wielokąt, który jest już wypukły, nie ma kieszeni.
Można utworzyć hierarchiczny opis dowolnego danego wielokąta, konstruując w ten sposób jego kadłub i kieszenie, a następnie rekurencyjnie tworząc hierarchię tego samego typu dla każdej kieszeni. Strukturę tę, zwaną drzewem różnic wypukłych , można skutecznie skonstruować.
Algorytmy
Znalezienie otoczki wypukłej wielokąta prostego można przeprowadzić w czasie liniowym . Odkryto, że kilka wczesnych publikacji na ten temat było błędnych, często dlatego, że prowadziły do stanów pośrednich ze skrzyżowaniami, które powodowały ich pękanie. Pierwszy poprawny algorytm czasu liniowego dla tego problemu został podany przez McCalluma i Avisa (1979) . Nawet po jego opublikowaniu nadal publikowano inne nieprawidłowe algorytmy. Brönnimann i Chan (2006) piszą, że większość opublikowanych algorytmów dla tego problemu jest niepoprawna, chociaż późniejsza historia zebrana przez Grega Aloupisa wymienia tylko siedem z piętnastu algorytmów jako niepoprawnych.
Szczególnie prosty algorytm dla tego problemu został opublikowany przez Grahama i Yao (1983) oraz Lee (1983) . Podobnie jak skanowania Grahama dla wypukłych kadłubów zbiorów punktów, jest on oparty na stosowej strukturze danych . Algorytm przemierza wielokąt w kolejności zgodnej z ruchem wskazówek zegara, zaczynając od wierzchołka, o którym wiadomo, że znajduje się na wypukłej otoczce (na przykład najbardziej wysunięty na lewo punkt). 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. Punkty w tej sekwencji to wierzchołki wielokąta wypukłego (niekoniecznie kadłub wszystkich dotychczas widzianych wierzchołków), który może mieć kieszenie przyczepione do niektórych jego krawędzi. 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. Kiedy przejście zgodnie z ruchem wskazówek zegara osiągnie punkt początkowy, algorytm jest zakończony, a stos zawiera wypukłe wierzchołki kadłuba w kolejności zgodnej z ruchem wskazówek zegara. Każdy krok algorytmu albo wypycha wierzchołek na stos, albo zdejmuje go ze stosu, a każdy wierzchołek jest wypychany i usuwany co najwyżej raz, więc całkowity czas algorytmu jest liniowy. Jeśli wierzchołki wejściowe są podane w tablicy w kolejności zgodnej z ruchem wskazówek zegara, dane wyjściowe można zwrócić w tej samej tablicy, używając tylko stałej liczby dodatkowych zmiennych jako pamięci pośredniej.
Podobną metodę można również zastosować do konstruowania wypukłych kadłubów fragmentarycznie gładkich krzywych zamkniętych w płaszczyźnie. Używając deque zamiast stosu, podobny algorytm można uogólnić na wypukły kadłub dowolnego łańcucha wielokątnego, a algorytm dla prostych wielokątów można uruchomić w dowolnym wierzchołku wielokąta, zamiast wymagać skrajnego wierzchołka jako wierzchołka początkowego .
Przerzucanie kieszeni
Odwrócenie kieszeni konstruuje nowy wielokąt z podanego, odzwierciedlając wielokątny łańcuch, który ogranicza kieszeń przez wypukłą krawędź kadłuba kieszeni . Każde odwrócenie tworzy inny prosty wielokąt o równym obwodzie i większej powierzchni, chociaż wiele jednoczesnych odwróceń może wprowadzić skrzyżowania. Odwrócenie dowolnie wybranej kieszeni, a następnie powtórzenie tego procesu z kieszeniami każdego kolejno utworzonego wielokąta, tworzy sekwencję prostych wielokątów. Zgodnie z twierdzeniem Erdősa – Nagya ten proces odwracania ostatecznie kończy się, osiągając wypukły wielokąt. Podobnie jak w przypadku problemu wypukłej konstrukcji kadłuba, problem ten ma długą historię błędnych dowodów.