Poligonalizacja
W geometrii obliczeniowej poligonalizacja skończonego zbioru punktów na płaszczyźnie euklidesowej jest prostym wielokątem , którego wierzchołkami są dane punkty. Poligonalizacja może być również nazywana poligonizacją , prostą poligonalizacją , wielokątem hamiltonowskim , nieprzecinającym się cyklem hamiltonowskim lub cyklem rozpinającym o prostych krawędziach bez przecinania się .
Każdy zbiór punktów, który nie leży na jednej prostej, ma co najmniej jedną poligonalizację, którą można znaleźć w czasie wielomianowym. Dla punktów w pozycji wypukłej jest tylko jeden, ale w przypadku niektórych innych zbiorów punktów może być ich wykładniczo wiele. Znalezienie optymalnej poligonalizacji w oparciu o kilka naturalnych kryteriów optymalizacji jest trudnym problemem, do którego zalicza się w szczególnym przypadku problem komiwojażera . Złożoność liczenia wszystkich poligonalizacji pozostaje nieznana.
Definicja
Poligonalizacja to prosty wielokąt mający dany zbiór punktów na płaszczyźnie euklidesowej jako zbiór wierzchołków. Wielokąt można opisać porządkiem cyklicznym na jego wierzchołkach, które są połączone kolejnymi parami odcinkami linii, krawędziami wielokąta. Tak zdefiniowany wielokąt jest „prosty”, jeśli jedyne punkty przecięcia tych odcinków linii znajdują się na wspólnych punktach końcowych.
Niektórzy autorzy rozważają poligonalizacja tylko dla punktów znajdujących się w położeniu ogólnym , co oznacza, że żadne trzy nie leżą na linii. Przy takim założeniu kąt pomiędzy dwoma kolejnymi odcinkami wielokąta nie może wynosić 180°. Jednakże, gdy rozważa się zbiory punktów z kolinearnością, ogólnie dopuszcza się, że ich poligonalizacja ma w niektórych punktach kąty 180°. Kiedy tak się dzieje, punkty te nadal uważa się za wierzchołki, a nie znajdujące się wewnątrz krawędzi.
Istnienie
Steinhaus (1964) zaobserwował, że każdy skończony punkt, w którym nie ma trójek, tworzy wierzchołki prostego wielokąta. Jednakże wymaganie, aby w linii nie było trzech graczy, jest niepotrzebnie zbyt silne. Zamiast tego wszystko, czego potrzeba do istnienia poligonalizacji (pozwalającej na kąty 180°), to to, że nie wszystkie punkty leżą na jednej linii. Jeśli tak nie jest, to mają poligonalizację, którą można skonstruować w czasie wielomianowym . Jednym sposobów konstruowania poligonalizacji jest wybranie dowolnego punktu wypukłym kadłubie P. {\ (niekoniecznie jeden z podanych punktów). Następnie promieniowe punktów wokół podstawie odległości od q) daje cykliczne uporządkowanie wielokąta w kształcie gwiazdy przechodzącego przez wszystkie dane punkty, z w jego jądrze. Ten sam pomysł sortowania punktów promieniowo wokół punktu centralnego jest stosowany w niektórych wersjach algorytmu ze skanowaniem Grahama i można go wykonać w czas. Poligonalizacja, która pozwala uniknąć kątów 180°, nie zawsze istnieje. Na przykład w przypadku siatek kwadratowych 3 × 3 i 5 × 5 we wszystkich poligonalizacjach stosuje się kąty 180°.
Oprócz poligonalizacji w kształcie gwiazdy, każdy niewspółliniowy zbiór punktów ma poligonalizację, która jest wielokątem monotonicznym . Oznacza to, że w odniesieniu do pewnej linii prostej (którą można przyjąć za oś linia prostopadła do linii odniesienia przecina wielokąt w jednym przedziale lub wcale. Konstrukcja Grünbauma (1994) rozpoczyna od posortowania punktów według ich i narysowania linii przechodzącej przez dwa skrajne punkty. Ponieważ punkty nie są w jednej linii, przynajmniej jeden z dwóch jest otwarty półpłaszczyzny ograniczone tą linią muszą być niepuste. Grünbaum tworzy dwa monotonne wielokątne łańcuchy łączące skrajne punkty poprzez posortowane podciągi punktów: jeden dla punktów tej niepustej otwartej półpłaszczyzny, a drugi dla pozostałych punktów. Ich związek jest pożądanym wielokątem monotonnym. Po etapie sortowania pozostałą część konstrukcji można wykonać w czasie liniowym .
Określenie, czy zbiór punktów ma poligonalizację przy użyciu tylko krawędzi równoległych do osi, jest NP-zupełne . Jednakże poligonalizacja z dodatkowym ograniczeniem polegającym na tym, że skręca w prawo w każdym wierzchołku, jeśli istnieje, jest określana jednoznacznie. Każda linia równoległa do osi przechodząca przez punkt musi przechodzić przez parzystą liczbę punktów, a ta poligonalizacja musi łączyć naprzemienne pary punktów na tej linii. Poligonalizację można znaleźć w czasie. grupując punkty według równych współrzędnych i sortując każdą grupę według drugiej współrzędnej. Dla dowolnego zbioru punktów co najwyżej jeden obrót może mieć poligonalizację tej postaci, a obrót ten można ponownie znaleźć w czasie wielomianowym.
Optymalizacja
Jaka jest złożoność obliczeniowa najdłuższej poligonalizacji?
Problemy znalezienia optymalnej poligonalizacji (dla różnych kryteriów optymalności) są często niewykonalne obliczeniowo. Na przykład rozwiązanie problemu komiwojażera dla danych punktów nie ma żadnych przecięć. Dlatego jest to zawsze poligonalizacja, poligonalizacja z minimalnym obwodem . Jest NP-trudny do znalezienia. Podobnie wiadomo, że znalezienie prostej poligonalizacji o minimalnej lub maksymalnej powierzchni jest NP-trudne i było przedmiotem pewnych wysiłków obliczeniowych. Maksymalna powierzchnia jest zawsze większa niż połowa powierzchni wypukłego kadłuba , dając współczynnik aproksymacji 2. Dokładna złożoność prostej poligonalizacji z maksymalnym obwodem i istnienie stałego współczynnika aproksymacji dla tego problemu pozostają nieznane. Poligonalizacja, która minimalizuje długość najdłuższej krawędzi, jest również trudna do znalezienia i trudna do przybliżenia do współczynnika przybliżenia niż nie jest znane żadne przybliżenie ze stałym współczynnikiem.
Nieoptymalne rozwiązanie problemu komiwojażera może obejmować skrzyżowania, ale możliwe jest wyeliminowanie wszystkich skrzyżowań poprzez lokalne kroki optymalizacji, które zmniejszają całkowitą długość. Używając kroków, które również eliminują przecięcia na każdym kroku, można to zrobić w czasie wielomianowym , ale bez tego ograniczenia istnieją lokalne sekwencje optymalizacyjne, które zamiast tego wykorzystują wykładniczą liczbę kroków.
Najkrótsza trasa bitoniczna (wielokąt monotoniczny o minimalnym obwodzie przechodzący przez dane punkty) jest zawsze poligonalizacją i można ją znaleźć w czasie wielomianowym.
Rachunkowość
Jaka jest złożoność obliczeniowa zliczania poligonalizacji?
Problem zliczania wszystkich poligonalizacji danego zbioru punktów należy do #P , klasy problemów zliczania związanych z problemami decyzyjnymi w NP . Nie wiadomo jednak, czy jest on #P-kompletny , a jeśli nie, jaka może być jego złożoność obliczeniowa. Zbiór punktów ma dokładnie jedną poligonalizację wtedy i tylko wtedy, gdy jest w pozycji wypukłej . Istnieją zbiory dla których liczba poligonalizacji jest aż najwyżej poligonalizacji.
Metody stosujące twierdzenie o separatorze planarnym do oznakowanych triangulacji punktów można zastosować do zliczenia wszystkich poligonalizacji zbioru punktów w czasie podwykładniczym. . Programowanie dynamiczne można wykorzystać do zliczenia wszystkich poligonalizacji monotonicznych w czasie wielomianowym, a wyniki tych obliczeń można następnie wykorzystać do wygenerowania losowej poligonalizacji monotonicznej.
Pokolenie
Czy ruchy lokalne mogą połączyć przestrzeń stanów poligonalizacji dla każdego zbioru punktów?
Nie wiadomo, czy jest możliwe, aby system wszystkich poligonalizacji utworzył połączoną przestrzeń stanów pod wpływem lokalnych ruchów, które zmieniają ograniczoną liczbę krawędzi poligonalizacji. Gdyby było to możliwe, można by go wykorzystać jako część algorytmu generowania wszystkich poligonalizacji poprzez zastosowanie przejścia grafu do przestrzeni stanów. W przypadku tego problemu nie wystarczy uwzględnić przewroty , które usuwają dwie krawędzie poligonalizacji i zastępują je dwiema innymi krawędziami, czyli przewroty VE które usuwają trzy krawędzie, z których dwie mają wspólny wierzchołek, i zastępują je trzema innymi krawędziami. Istnieją poligonalizacja, dla których nie jest możliwe żadne odwrócenie ani odwrócenie VE, mimo że ten sam zbiór punktów ma inne poligonalizacja.
Zawinięcia wielokątne , słabo proste wielokąty, które wykorzystują każdy dany punkt jeden lub więcej razy jako wierzchołek, obejmują wszystkie poligonalizacja i są połączone lokalnymi ruchami. Inna, bardziej ogólna klasa wielokątów, otaczające wielokąty , to proste wielokąty, które mają niektóre z podanych punktów jako wierzchołki i obejmują wszystkie punkty. Są one ponownie połączone lokalnie i można je wyświetlić w czasie wielomianowym na wielokąt. Algorytm konstruuje drzewo wielokątów, którego wypukła otoczka , a rodzic każdego innego otaczającego wielokąta uzyskany poprzez usunięcie jednego wierzchołka (co udowodniono, stosując metodę twierdzenie o dwojgu uszach o zewnętrznej stronie wielokąta). Następnie stosuje algorytm wyszukiwania wstecznego do tego drzewa, aby wyświetlić listę wielokątów. konsekwencji tej metody wszystkie poligonalizacja mogą być czasie wykładniczym ( dla .
Aplikacje
Klasyczne łamigłówki typu „Połącz kropki” polegają na łączeniu punktów po kolei w celu uzyskania nieoczekiwanego kształtu, często bez skrzyżowań. Problem komiwojażera i jego warianty mają wiele zastosowań. Poligonalizacja ma również zastosowanie w rekonstrukcji linii konturowych na podstawie rozproszonych punktów danych oraz w śledzeniu granic w analizie obrazu .
Zobacz też
- Twierdzenie Denjoya-Riesza o zbiorach nieskończenie wielu punktów, które można połączyć łukiem Jordana