Erkennen von zwei Arten von fast einfachen Polygonen

Ich interessiere mich für die Komplexität der Entscheidung, ob ein bestimmtes nicht einfaches Polygon fast einfach ist, und zwar in einer von zwei verschiedenen formalen Richtungen: schwach einfach oder nicht selbstüberschreitend . Da diese Begriffe nicht allgemein bekannt sind, möchte ich mit einigen Definitionen beginnen.

Ein Polygon ist der geschlossene Kreis von Liniensegmenten, die eine endliche Folge von Punkten in der Ebene verbinden. Die Punkte heißen die Eckpunkte des Polygons, und die Segmente heißen seine Kanten . Wir können jedes Polygon angeben, indem wir seine Eckpunkte in der richtigen Reihenfolge auflisten. $P$ $p_0, p_1, p_2, \dots, p_{n-1}$ $p_i$ $p_i p_{i+1\bmod n}$
Ein Polygon ist einfach, wenn alle $n$ Eckpunkte verschieden sind und sich Kanten nur an ihren Endpunkten schneiden. Entsprechend ist ein Polygon einfach, wenn es zu einem Kreis homöomorph ist und jede Kante eine positive Länge hat. Im Allgemeinen können sich die Eckpunkte und Kanten eines Polygons jedoch willkürlich schneiden oder sogar zusammenfallen. ¹
Betrachten Sie zwei polygonale Pfade und deren Schnittpunkt ein gemeinsamer Unterpfad von beiden ist (möglicherweise ein einzelner Punkt). Wir sagen, dass sich und kreuzen, wenn sich ihre Endpunkte an der Grenze einer Nachbarschaft des gemeinsamen Unterpfads abwechseln . Ein Polygon kreuzt sich selbst, wenn es zwei sich kreuzende Unterpfade hat und sich ansonsten nicht selbst kreuzt . ² $A$ $B$ $A$ $B$ $A(0), B(0), A(1), B(1)$ $A\cap B$
Ein Polygon ist schwach einfach, wenn es die Grenze einer Folge einfacher Polygone ist, oder gleichwertig, wenn es eine willkürlich kleine Störung der Eckpunkte gibt, die das Polygon einfach macht. Jedes schwach einfache Polygon ist nicht selbstüberschreitend; Einige sich nicht selbst kreuzende Polygone sind jedoch nicht schwach einfach.

Betrachten Sie beispielsweise die unten gezeigten sechs Punkte $a,b,p,q,x,y$ .

Bildbeschreibung hier eingeben

Das Polygon $abpqyz$ ist einfach; siehe die linke Abbildung.
Das Polygon $papbpqyqzq$ ist schwach einfach; Die mittlere Abbildung zeigt ein einfaches Polygon in der Nähe. Dieses Polygon ist jedoch nicht einfach, da es $p$ dreimal besucht.
Das Polygon sich selbst, weil sich die Unterpfade und kreuzen. Sehen Sie die rechte Abbildung für etwas Intuition. $papbpqzqyq$ $bpqz$ $yqpa$
Schließlich ist das Polygon (das sich zweimal um das mittlere Polygon windet) nicht selbst kreuzend, aber es ist nicht schwach einfach. Intuitiv ist die Umdrehungszahl dieses Polygons , während die Umdrehungszahl jedes einfachen Polygons . (Ein formaler Beweis erfordert einige Fallanalysen, zum Teil, weil die Umdrehungszahl für Polygone mit Winkeln von nicht genau definiert ist !) $papbpqyqzqpapbpqyqzq$ $\pm 2$ $\pm 1$ $0^\circ$

Update (13. September): In der folgenden Abbildung ist das Polygon nicht selbstkreuzend und hat die Nummer 1 , ist aber nicht ganz einfach. Das Polygon hat vermutlich mehrere sich kreuzende, nicht einfache Unterwege , aber keine sich kreuzenden, einfachen Unterwege . (Ich sage "wohl", weil es unklar ist, wie man definiert, wenn sich zwei nicht einfache Wege kreuzen!) $abcabcxyzxpqrxzyx$

Zum Schluss hier meine eigentlichen Fragen:

Wie schnell können wir feststellen, ob ein bestimmtes Polygon sich nicht selbst kreuzt?
Wie schnell können wir feststellen, ob ein bestimmtes Polygon schwach einfach ist?

Das erste Problem kann wie folgt in gelöst werden. Da es Vertices gibt, gibt es Vertex-to-Vertex-Unterpfade; Wir können testen, ob ein bestimmter Unterpfad in der Zeit einfach ist (durch rohe Gewalt). Für jedes Paar einfacher Vertex-zu-Vertex-Unterpfade können wir testen, ob sie sich in -Zeit kreuzen . Dies kann jedoch nicht der bestmögliche Algorithmus sein. $O(n^5)$ $n$ $O(n^2)$ $O(n^2)$ $O(n)$

Ich weiß nicht, ob das zweite Problem in Polynomzeit gelöst werden kann. Ich denke, ich kann für jedes nicht einfache Polygon schnell eine genau definierte Abbiegezahl berechnen (es sei denn, die Vereinigung der Polygonkanten ist nur ein Pfad. In diesem Fall muss das Polygon schwach einfach sein). Siehe meine Antwort unten. Das obige neue Beispielpolygon impliziert jedoch, dass Nicht-Selbstkreuzung und Wenden Nummer 1 nicht schwach einfach implizieren.

Wir können feststellen , ob ein bestimmtes Polygon ist einfach in Zeit durch jedes Paar von Kanten für Schnittprüfung oder in Zeit , um eine Standard - sweepline Algorithmus, oder sogar in Zeit mit Chazelles Triangulationsalgorithmus. (Wenn das Eingabepolygon nicht einfach ist, löst jeder Triangulationsalgorithmus entweder eine Ausnahme, eine Endlosschleife oder eine Ausgabe aus, die keine gültige Triangulation ist.) Keiner dieser Algorithmen löst jedoch die von mir gestellten Probleme. $O(n^2)$ $O(n\log n)$ $O(n)$

¹ Branko Grünbaum. Polygone: Meister hatte Recht und Poinsot hatte Unrecht, setzte sich aber durch . Beiträge zur Algebra und Geometrie 53 (1): 57–71, 2012.

² Siehe zum Beispiel: Erik D. Demaine und Joseph O'Rourke. Geometrische Faltungsalgorithmen: Verknüpfungen, Origami, Polyeder . Cambridge University Press, 2007.

ds.algorithms cg.comp-geom polygon Jeffε
quelle

Ich verstehe nicht, warum man diese Frage runterstimmen würde ?!

Kaveh

Ich mag die Frage völlig missverstehen, und so ist sie vielleicht weit entfernt, aber es scheint mir, dass die Art und Weise, wie Sie Eckpunkte zählen, bedeutet, dass die zweite Frage notwendigerweise exponentielle Zeit in Anspruch nimmt. Lassen Sie mich erklären: In Ihrem letzten Beispiel verwenden Sie dieselben Eckpunkte mehrmals. Es scheint einfach zu sein, Graphen mit einer exponentiellen Anzahl eindeutiger Zyklen zu konstruieren.

Joe Fitzsimons

Wenn Ihre Eingabe das in Ihren Beispielen angegebene Polygon ist, ist es möglich, dass die Eingabe in Bezug auf die Anzahl der Scheitelpunkte exponentiell ist, ohne dass ein Zyklus wiederholt wird. Wenn der Graph Ihren Beispielgraphen (2 und 3) als Untergraphen enthält, dann hat er Zyklen, die sich nicht kreuzen und Zyklen, die sich kreuzen. Daher müssen Sie die gesamte Zeichenfolge lesen, um sicherzustellen, dass Sie keine Kreuzungszyklen haben (die möglicherweise enthalten sind oder nicht). Dies dauert im schlimmsten Fall in zeitlich exponentiell .

n

$n$

Joe Fitzsimons

@JoeFitzsimons: Die Eingabe ist nur eine Folge von Punkten (dh Paaren von reellen Zahlen), die nicht eindeutig sein müssen. Die Eingabegröße ist die Länge dieser Sequenz, nicht die Anzahl der eindeutigen Punkte.

n

$n$

Jeffs

@Kaveh: Vielleicht zu abstrakt / spezialisiert? Zu viele Wörter? Ich hätte die Punkte Ga, Ka, Naa, Taa, Tin, Khat benennen sollen ?

Jeffs

Antworten:

Es scheint, als hätte die erste Frage einen -Algorithmus (obwohl dies wahrscheinlich auch nicht optimal ist). Unter der Annahme, dass es eine Kreuzung gibt, scheint der Schlüssel zum Finden zu sein, dass die Kanten, die gefunden werden müssen, diejenigen sind, die sich unmittelbar auf beiden Seiten des gemeinsamen Unterpfads befinden. Daher betrachten wir alle Paare aufeinanderfolgender Kantenpaare. Davon gibt es eine quadratische Anzahl. Wenn wir ein Paar Kantenpaare mit Eckpunkten und so dass die Kanten und sind, folgen wir dem gemeinsamen Unterpfad bis zum Ende und untersuchen die Kanten, die ihn verlassen. Wenn sie zusammen mit und eine Kreuzung bilden $O(n^3)$ $abc$ $def$ $bc$ $ef$ $ab$ $de$ , dann sind wir fertig, sonst fahren wir mit dem nächsten Paar fort. Dem gemeinsamen Unterpfad zu folgen ist höchstens eine lineare Zeitoperation, daher ist der gesamte Algorithmus . $O(n^3)$

Diese Analyse ist wahrscheinlich nicht eng, da die Häufigkeit, mit der ein gemeinsamer Unterpfad linearer Länge befolgt wird, in der Anzahl der Paare von Paaren nicht linear ist. Es sollte nur eine konstante Anzahl davon geben. Wenn die Länge des längsten gemeinsamen Unterpfads konstant ist, ist die Zeit, die gemeinsamen Unterpfaden folgt, in Ordnung. Ich würde erwarten, dass der schlimmste Fall eintritt, wenn es einen einzelnen Unterpfad der Länge gibt, der -Unterpfaden gemeinsam ist. Dann gibt es Wechselwirkungen und in jeder Wechselwirkung werden Kanten verfolgt. Die Anzahl der Kanten, denen gefolgt wird, ist also immer noch $O(\sqrt{n})$ $O(\sqrt{n})$ $O(n)$ $O(\sqrt{n})$ $o(n^2)$ und die Grenze ergibt sich aus der Anzahl der Paare. Daher würde ich vermuten, dass die wahre Schranke für diesen Algorithmus . $O(n^2)$

Chris Gray
quelle

"Dem gemeinsamen Unterpfad zu folgen ist höchstens eine lineare Zeitoperation ..." Stimmt das? Beachten Sie, dass die Unterpfade nicht identisch sind. Einer kann sich entlang des Bildes des anderen hin und her falten. Tatsächlich ist mir nicht einmal klar, wann Sie wissen, dass Sie fertig sind.

Pat Morin

Guter Punkt. Wäre es möglich, das Polygon als Vorverarbeitungsschritt in eine Art Standardform zu bringen? Wir würden Pfade auslassen, die sich sofort auf sich selbst zurückfalten, sowie Scheitelpunkte, die mit ihren unmittelbaren Nachbarn kollinear sind. Dann wäre der Satz, den Sie zitiert haben, besser definiert - der gemeinsame Unterpfad besteht aus Kanten, die dieselben Eckpunkte haben, und Sie wissen, dass Sie fertig sind, weil Sie verschiedene Eckpunkte treffen. Der Nachweis, dass die Antwort im Polygon in der Standardform dieselbe bleibt, sollte nicht zu schwierig sein.

Chris Gray

@ ChrisGray: Vielleicht, aber nicht ganz so einfach, wie Sie vorgeschlagen haben. Wenn das Bild von ein Baum ist, wird durch rekursives Eliminieren aller Switchbacks auf einen einzelnen Punkt reduziert .

P

$P$

P

$P$

Jeffs

Ja, du hast recht, diese Idee wird nicht funktionieren. Die Zahl ganz rechts, die Sie oben angegeben haben, wird auf einen Punkt reduziert.

Chris Gray

Ich habe vor, das Kopfgeld auslaufen zu lassen. Die Hälfte der Punkte wird automatisch für diese Antwort vergeben.

Jeffs

Auf Vorschlag von Pat Morin ist hier meine Idee zur Berechnung der Abbiegezahl. Tut mir leid, wenn das etwas schlampig ist; Ich kämpfe immer noch gegen die Dämonen. Außerdem zeigt Pats Kommentar zu Chris 'Antwort, dass ich einige wichtige entartete Fälle ignoriert habe. Aber ich werde es trotzdem hier posten, falls andere es nützlich finden.

Für jeden Index sei der vorzeichenbehaftete Außenwinkel am Scheitelpunkt ; Dies ist der Winkel gegen den Uhrzeigersinn zwischen den Strahlen und , normalisiert auf den Bereich . (Alle Index Arithmetik ist implizit mod ) . Die Drehzahl von ist definiert als Lassen Sie uns rufen eine Ecke einen Sporn , wenn der Innenwinkel an $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}}$ $-\pi \le \theta_i \le \pi$ $n$ $P$

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$ ist gleich . Der äußere Winkel ; an einem Sporn ist nicht genau definiert; es könnte entweder oder . Allgemeiner ist die Umdrehungszahl von genau dann definiert, wenn keine Spurs hat (und keine wiederholten Eckpunkte ). Es ist nicht schwer zu beweisen, dass eine ganze Zahl ist, wenn es gut definiert ist. insbesondere gilt wenn ein einfaches Polygon ist.

0

$0$

θ_{i}

$\theta_i$

π

$\pi$

- π

$-\pi$

P

$P$

P

$P$

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$

Angenommen, enthält einen Weg der Form , wobei und der Pfad die Umkehrung von ist Pfad . Dann ist ein Sporn; nenne die Wurzel von . In diesem Fall lassen Sie uns definieren den Außenwinkel bei wie folgt: (Aber was ist, wenn $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$ ? Wie Pat bemerkt, kann dies tatsächlich passieren. Wahrscheinlich gibt es auch in diesem Fall eine Art rekursiven Weg, um zu definieren , aber ich weiß nicht, was es ist.) $\tilde\theta(s)$

Wenn schwach einfach ist, dann gibt es ein einfaches -gon beliebig nahe bei ; Tet ist der Scheitelpunkt von , der nächsten liegt . Wie nähert sich , den Innenwinkel bei Null nähert. Es ist nicht schwer zu beweisen (durch Induktion über die Länge von ), dass sich der äußere Winkel nähert . $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)$

Wenn vollständig aus einem besteht, dem die Umkehrung folgt: , sind die Außenwinkel an den Ausläufern und noch nicht genau definiert. Aber in diesem Fall glaube ich, dass genau dann schwach einfach ist, wenn der Weg nicht ist. (Es gibt komplexere Fälle, in denen ich keine vernünftige geänderte Abbiegezahl definieren kann, insbesondere wenn das Polygon auf einem einzigen Gang vor- und zurückwandert. In all diesen Fällen scheint das Polygon jedoch nur dann schwach einfach zu sein, wenn es es ist ist nicht selbstüberschreitend.) $P$ $r\mathord\leadsto s\mathord\leadsto r$ $r$ $s$ $P$ $r\mathord\leadsto s$

Andernfalls haben wir, wenn wir für einen Nicht-Stichvertex , eine genau definierte Wendezahl , was muss, wenn schwach einfach ist. $\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$

Ich bin nicht mehr sicher, dass in linearer Zeit berechnet werden kann. Die Hauptschwierigkeit besteht darin, dass die selbst Sporen enthalten können. Der naive Algorithmus, der die Wurzel jedes Sporns durch rohe Gewalt findet, benötigt im schlimmsten Fall tatsächlich Zeit; Betrachten Sie ein gon mit einem Subwalk der Länge , der einfach zwischen zwei Punkten wechselt. $\widetilde{Turn}(P)$ $r\mathord\leadsto s$ $\Theta(n^2)$ $n$ $\Omega(n)$

Jeffε
quelle