Wykrywanie dwóch rodzajów prawie prostych wielokątów

Interesuje mnie złożoność decydowania, czy dany nie-prosty wielokąt jest prawie prosty, w jednym z dwóch różnych formalnych zmysłów: słabo prostym lub nie-samokreślącym . Ponieważ te terminy nie są powszechnie znane, zacznę od niektórych definicji.

Wieloboku jest zamknięty cykl odcinków łączenia kilku skończoną sekwencję punkty na płaszczyźnie. Punkty nazywane są wierzchołkami wielokąta, a segmenty nazywane są jego krawędziami . Możemy określić dowolny wielokąt, po prostu wymieniając jego wierzchołki w kolejności. $P$ $p_0, p_1, p_2, \dots, p_{n-1}$ $p_i$ $p_i p_{i+1\bmod n}$
Wielokąt jest prosty, jeśli wszystkie $n$ wierzchołków są różne, a krawędzie przecinają się tylko w punktach końcowych. Odpowiednio, wielokąt jest prosty, jeśli jest homeomorficzny dla koła, a każda krawędź ma długość dodatnią. Ogólnie jednak wierzchołki i krawędzie wielokąta mogą przecinać się dowolnie, a nawet pokrywać. ¹
Rozważ dwie ścieżki wielokątne $A$ i $B$ których przecięcie jest wspólną podścieżką obu (być może pojedynczym punktem). Mówimy, że i krzyż , jeśli ich punkty końcowe zastępcy na granicy dzielnicy wspólnej podścieżkę . Wielobok sam się krzyżuje, jeśli ma dwie przecinające się podścieżki, a w przeciwnym razie nie krzyżuje się . ²⁾ $A$ $B$ $A(0), B(0), A(1), B(1)$ $A\cap B$
Wielobok jest słabo prosty, jeśli stanowi granicę sekwencji prostych wieloboków lub równoważnie, jeśli występuje dowolnie mała perturbacja wierzchołków, która sprawia, że wielobok jest prosty. Każdy słabo prosty wielokąt nie przechodzi przez siebie; jednak niektóre wielokąty nieprzekraczające się nie są dość proste.

Rozważmy na przykład sześć punktów $a,b,p,q,x,y$ pokazanych poniżej.

wprowadź opis zdjęcia tutaj

Wielokąt $abpqyz$ jest prosty; patrz lewa postać.
Wielobok $papbpqyqzq$ jest słabo prosty; środkowa figura pokazuje pobliski prosty wielokąt. Jednak ten wielokąt nie jest prosty, ponieważ odwiedza $p$ trzy razy.
Wielobok to samo przejście, ponieważ podścieżki i krzyż. Zobacz odpowiednią liczbę dla intuicji. $papbpqzqyq$ $bpqz$ $yqpa$
Wreszcie, wielokąt (który nakręca dwukrotnie wokół środkowego wielokąta) jest non-self-przejście, ale to nie słabo proste. Intuicyjnie liczba zwrotna tego wielokąta wynosi , podczas gdy liczba zwrotna dowolnego prostego wielokąta musi wynosić . (Formalny dowód wymaga pewnej analizy przypadku, częściowo dlatego, że liczba zwrotów nie jest właściwie dobrze zdefiniowana dla wielokątów z kątami !) $papbpqyqzqpapbpqyqzq$ $\pm 2$ $\pm 1$ $0^\circ$

Aktualizacja (13 września): Na poniższym rysunku wielokąt nie przechodzi przez siebie i ma zwrot 1 , ale nie jest to wcale takie proste. Wielokąt ma prawdopodobnie kilka przecinających się niełatwych ścieżek , ale nie ma żadnych prostych ścieżek . (Mówię „prawdopodobnie”, ponieważ nie jest jasne, jak określić, kiedy krzyżują się dwa niełatwe spacery!) $abcabcxyzxpqrxzyx$

Na koniec oto moje aktualne pytania:

Jak szybko możemy ustalić, czy dany wielokąt nie przechodzi przez siebie?
Jak szybko możemy ustalić, czy dany wielokąt jest słabo prosty?

Pierwszy problem można rozwiązać w czasie w następujący sposób. Ponieważ istnieje wierzchołków, istnieją podścieżki wierzchołków ; możemy sprawdzić, czy jakaś konkretna podścieżka jest prosta w czasie (brutalną siłą). Dla każdej pary prostych podścieżek wierzchołek-wierzchołek możemy sprawdzić, czy przecinają się w czasie . Ale to nie może być najlepszy możliwy algorytm. $O(n^5)$ $n$ $O(n^2)$ $O(n^2)$ $O(n)$

Nie wiem, czy drugi problem można rozwiązać w czasie wielomianowym. Myślę, że mogę szybko obliczyć dobrze zdefiniowaną liczbę zwrotną dla dowolnego nieprostego wielokąta (chyba że połączenie krawędzi wielokąta jest tylko ścieżką, w którym to przypadku wielokąt musi być słabo prosty); zobacz moją odpowiedź poniżej. Jednak nowy przykładowy wielokąt powyżej sugeruje, że brak przekraczania i obracanie numeru 1 nie oznacza słabo prostej.

Można określić, czy dana wielokąt jest prosty w w czasie sprawdzając każdą parę krawędziami przecięcia lub razem za pomocą standardowego algorytmu sweepline lub nawet w Czas za pomocą algorytmu triangulacji Chazelle. (Jeśli wielokąt wejściowy nie jest prosty, dowolny algorytm triangulacji wyrzuci wyjątek, pętlę nieskończoną lub wygeneruje dane wyjściowe, które nie są prawidłową triangulacją.) Ale żaden z tych algorytmów nie rozwiązuje problemów, o które pytam. $O(n^2)$ $O(n\log n)$ $O(n)$

¹ Branko Grünbaum. Wieloboki: Meister miał rację, a Poinsot mylił się, ale zwyciężył . Beiträge zur Algebra und Geometrie 53 (1): 57–71, 2012.

² Patrz na przykład: Erik D. Demaine i Joseph O'Rourke. Geometryczne algorytmy składania: powiązania, origami, wielościany . Cambridge University Press, 2007.

ds.algorithms cg.comp-geom polygon Jeffε
źródło

Nie rozumiem, dlaczego głosować na to pytanie z góry ?!

Kaveh

Być może całkowicie nie rozumiem pytania, a więc może jest to całkiem dalekie, ale wydaje mi się, że sposób liczenia wierzchołków oznacza, że drugie pytanie z konieczności zajmuje wykładniczy czas. Pozwól, że wyjaśnię: w ostatnim przykładzie wielokrotnie używasz tych samych wierzchołków. Konstruowanie wykresów, w których występuje wykładnicza liczba unikalnych cykli, wydaje się łatwe.

Joe Fitzsimons

Jeśli dane wejściowe są wielokątami podanymi jak w przykładach, możliwe jest, że dane wejściowe będą wykładnicze w liczbie wierzchołków bez powtarzania cyklu. Jeśli wykres zawiera przykładowy wykres (2 i 3) jako podgraf, oznacza to, że cykle się nie krzyżują, a cykle się krzyżują. W rezultacie musisz przeczytać cały ciąg, aby upewnić się, że nie masz żadnych cykli krzyżowania (które mogły, ale nie zostały uwzględnione). To wymaga czasu potęgę naturalną o wykładniku w w najgorszym przypadku.

n

$n$

Joe Fitzsimons

@JoeFitzsimons: Dane wejściowe to tylko sekwencja punktów (tj. Par liczb rzeczywistych), które nie muszą być odrębne. Rozmiar wejściowy to długość tej sekwencji, a nie liczba unikalnych punktów.

n

$n$

Jeffε

@Kaveh: Może zbyt abstrakcyjny / specjalistyczny? Zbyt wiele słow? Powinienem nazwać punkty Ga, Ka, Naa, Taa, Tin, Khat ?

Jeffε

Odpowiedzi:

Wydaje się, że pierwsze pytanie ma algorytm (choć prawdopodobnie nie jest to również optymalne). Zakładając, że istnieje skrzyżowanie, kluczem do jego znalezienia wydaje się, że krawędzie, które należy znaleźć, są krawędziami znajdującymi się bezpośrednio po obu stronach wspólnej podścieżki. Dlatego patrzymy na wszystkie pary kolejnych par krawędzi. Jest ich kwadratowa liczba. Jeśli znajdziemy parę krawędzi z wierzchołkami i tak że krawędzie i są takie same, wówczas podążamy wspólną ścieżką podrzędną do końca i sprawdzamy krawędzie, które ją opuszczają. Jeśli tworzą skrzyżowanie z i $O(n^3)$ $abc$ $def$ $bc$ $ef$ $ab$ $de$ , to skończymy, w przeciwnym razie przejdziemy do następnej pary. Podążanie za wspólną ścieżką podrzędną jest co najwyżej operacją w czasie liniowym, więc cały algorytm to . $O(n^3)$

Ta analiza prawdopodobnie nie jest ścisła, ponieważ liczba wspólnych podścieżek o długości liniowej nie jest liniowa w liczbie par. Powinno być ich tylko stała liczba. Podobnie, jeśli długość najdłuższej wspólnej podścieżki jest stała, to jesteśmy w porządku pod względem ilości czasu po wspólnych podścieżkach. Spodziewałbym się, że najgorszy przypadek występuje, gdy istnieje jedna podścieżka o długości która jest wspólna dla podścieżek . Następnie występują interakcje i w każdej interakcji śledzone są krawędzie . Więc nawet liczba śledzonych krawędzi wynosi $O(\sqrt{n})$ $O(\sqrt{n})$ $O(n)$ $O(\sqrt{n})$ $o(n^2)$ , a granica wynika z liczby par. Tak więc zgaduję, że prawdziwą granicą tego algorytmu jest . $O(n^2)$

Chris Gray
źródło

„Podążanie wspólną ścieżką podrzędną jest co najwyżej operacją w czasie liniowym ...” Czy to prawda? Pamiętaj, że podścieżki nie są identyczne. Jeden może składać się tam iz powrotem wzdłuż obrazu drugiego. W rzeczywistości nie jest (dla mnie) jasne, kiedy wiesz, że skończyłeś.

Pat Morin

Słuszna uwaga. Czy byłoby możliwe, w ramach etapu wstępnego przetwarzania, umieścić wielokąt w jakiejś standardowej formie? Uciekalibyśmy ścieżkami, które natychmiast się odkładają, a także wierzchołkami, które są współliniowe z ich bezpośrednimi sąsiadami. Wtedy zdanie, które zacytowałbyś, byłoby lepiej zdefiniowane - wspólna podścieżka składa się z krawędzi, które mają te same wierzchołki, i wiesz, że zrobiono to, ponieważ trafiłeś różne wierzchołki. Udowodnienie, że odpowiedź pozostaje taka sama w wielokącie w standardowej formie, nie powinno być zbyt trudne.

Chris Gray

@ChrisGray: Może, ale nie tak łatwo, jak sugerowałeś. Jeśli obraz jest drzewem, to rekurencyjnie wymykając się wszystkim zwrotom, ostatecznie zmniejsza do jednego punktu.

P

$P$

P

$P$

Jeffε

Tak, masz rację, ten pomysł nie zadziała. Prawa liczba, którą podałeś powyżej, zostanie zredukowana do jednego punktu.

Chris Gray

Mam zamiar pozwolić, aby nagroda wygasła; połowa punktów zostanie automatycznie przyznana na tę odpowiedź.

Jeffε

Zgodnie z sugestią Pata Morina, oto mój pomysł na obliczenie liczby zwrotnej. Przepraszam, jeśli to trochę niechlujne; Wciąż walczę z demonami notacji. Co więcej, komentarz Pata do odpowiedzi Chrisa pokazuje, że zignorowałem kilka ważnych zdegenerowanych przypadków. Ale i tak opublikuję tutaj, na wypadek gdyby inni uznali to za przydatne.

Dla dowolnego indeksu , niech oznacza podpisany kąt zewnętrzny w wierzchołku ; jest to kąt przeciwny do ruchu wskazówek zegara między promieniami i , znormalizowany do zakresu $i$ $\theta(p_i) = \theta(p_{i-1}, p_i, p_{i+1})$ $p_i$ $\overrightarrow{p_{i-1}p_i}$ $\overrightarrow{p_ip_{i+1}}$ . (Wszystkie arytmetyczna indeks jest niejawnie mod ). Określenie obracając liczbę od jest zdefiniowana jako $-\pi \le \theta_i \le \pi$ $n$ $P$ Zadzwonię wierzchołekbodziec, jeśliwewnętrznykąt przyjest równa. Kąt zewnętrznyna ostrodze nie jest dobrze określony; może to byćlub. Mówiąc bardziej ogólnie, liczba zwrotówjest dobrze zdefiniowana wtedy i tylko wtedy, gdynie ma ostróg (i nie ma powtarzających się wierzchołków

T u r n (P) = \frac{1}{2 π} \sum_{i = 0}^{n - 1} θ (p_{i}) .

$Turn(P) = \frac{1}{2\pi} \sum_{i=0}^{n-1} \theta(p_i).$

p_{i}

$p_i$

p_{i}

$p_i$

0

$0$

θ_{i}

$\theta_i$

π

$\pi$

- π

$-\pi$

P

$P$

P

$P$

). Nie jest to trudne do wykazania, że

jest liczbą całkowitą, jeśli jest dobrze zdefiniowane; w szczególności

, jeśli

jest prosty wielokąta.

p_{i} = p_{i + 1}

$p_i=p_{i+1}$

T u r n (P)

$Turn(P)$

T u r n (P) = \pm 1

$Turn(P) = \pm 1$

P

$P$

$P$ $p\mathord\to r\mathord\leadsto s\mathord\leadsto r\mathord\to q$ $p\ne q$ $r\mathord\leadsto s$ $s\mathord\leadsto r$ $s$ $r$ $s$ $s$

\tilde{θ} (s) = π \cdot s g n θ (p, r, q) = {\begin{cases} π & if θ (p, r, q) > 0 \\ - π & if θ (p, r, q) < 0 \end{cases}

$\tilde\theta(s) = \pi \cdot \mathop{sgn}\theta(p, r, q) = \begin{cases} \pi & \text{if } \theta(p, r, q) > 0\\ -\pi & \text{if } \theta(p, r, q) < 0 \end{cases}$ $\theta(p,r,q)=0$ $\tilde\theta(s)$ nawet w tym przypadku, ale nie wiem co to jest.)

$P$ $n$ $\tilde{P}$ $P$ $\tilde{s}$ $\tilde{P}$ $P$ $\tilde{P}$ $P$ $\tilde{s}$ $r\mathord\leadsto s$ $\theta(\tilde{s})$ $\tilde\theta(s)$

$P$ $r\mathord\leadsto s\mathord\leadsto r$ $r$ $s$ $P$ $r\mathord\leadsto s$

$\tilde\theta(p_i) = \theta(p_i)$ $p_i$ $\widetilde{Turn}(P) = \sum_i\tilde\theta(p_i)/2\pi = Turn(\tilde{P})$ $\pm 1$ $P$

$\widetilde{Turn}(P)$ $r\mathord\leadsto s$ $\Theta(n^2)$ $n$ $\Omega(n)$

Jeffε
źródło