Detectando dos tipos de polígonos casi simples

Estoy interesado en la complejidad de decidir si un polígono no simple dado es casi simple, en cualquiera de los dos sentidos formales diferentes: débilmente simple o no autocruzamiento . Dado que estos términos no son ampliamente conocidos, permítanme comenzar con algunas definiciones.

• Un polígono es el ciclo cerrado de segmentos de línea que conectan una secuencia finita de puntos en el plano. Los puntos se llaman vértices del polígono, y los segmentos se llaman sus bordes . Podemos especificar cualquier polígono simplemente enumerando sus vértices en orden.$P$$p_0, p_1, p_2, \dots, p_{n-1}$$p_i$$p_i p_{i+1\bmod n}$

• Un polígono es sencilla si todos los $n$ vértices son distintos y los bordes se cruzan solamente en sus extremos. De manera equivalente, un polígono es simple si es homeomorfo a un círculo y cada borde tiene una longitud positiva. Sin embargo, en general, los vértices y los bordes de un polígono pueden cruzarse arbitrariamente o incluso coincidir. ¹

• Considere dos rutas poligonales $A$ y $B$ cuya intersección es una subruta común de ambas (posiblemente un solo punto). Decimos que $A$ y $B$ cruz si sus puntos finales $A(0), B(0), A(1), B(1)$ se alternan en el límite de una zona común de la subtrazado $A\cap B$ . Un polígono se cruza automáticamente si tiene dos subrutas cruzadas y, de lo contrario, no se cruza . ²

• Un polígono es débilmente simple si es el límite de una secuencia de polígonos simples, o de manera equivalente, si hay una perturbación arbitrariamente pequeña de los vértices que hace que el polígono sea simple. Cada polígono débilmente simple no se cruza a sí mismo; sin embargo, algunos polígonos que no se cruzan no son débilmente simples.

Por ejemplo, considere los seis puntos $a,b,p,q,x,y$ muestran a continuación.

• El polígono $abpqyz$ es simple; Ver la figura de la izquierda.

• El polígono $papbpqyqzq$ es débilmente simple; la figura del medio muestra un polígono simple cercano. Sin embargo, este polígono no es simple, porque visita $p$ tres veces.

• El polígono se sí mismo, porque los subrutas y cruzan. Vea la figura correcta para un poco de intuición.b p q z y q p $papbpqzqyq$$bpqz$$yqpa$

• Por último, el polígono (que serpentea dos veces alrededor del polígono medio) no es auto-cruce, pero es no sencilla débilmente. Intuitivamente, el número de giro de este polígono es , mientras que el número de giro de cualquier polígono simple debe ser . (¡Una prueba formal requiere un análisis de casos, en parte porque el número de giro no está realmente bien definido para polígonos con ángulos !)± 2 ± 1 0 $papbpqyqzqpapbpqyqzq$$\pm 2$$\pm 1$$0^\circ$

Actualización (13 de septiembre): en la figura a continuación, el polígono no se cruza automáticamente y tiene el número de giro 1 , pero no es débilmente simple. Podría decirse que el polígono tiene varios subwalks no simples de cruce , pero no tiene subpaths simples de cruce . (Digo "posiblemente" porque no está claro cómo definir cuándo se cruzan dos paseos no simples).$abcabcxyzxpqrxzyx$

Entonces, finalmente, aquí están mis preguntas reales:

• ¿Qué tan rápido podemos determinar si un polígono dado no se cruza a sí mismo?

• ¿Qué tan rápido podemos determinar si un polígono dado es débilmente simple?

El primer problema se puede resolver en tiempo siguiente manera. Como hay vértices, hay subárboles de vértice a vértice; podemos probar si algún subpaso en particular es simple en el tiempo (por fuerza bruta). Para cada par de subrutas simples de vértice a vértice, podemos probar si se cruzan en el tiempo . Pero este no puede ser el mejor algoritmo posible.n O ( n 2 ) O ( n 2 ) O ( n $O(n^5)$$n$$O(n^2)$$O(n^2)$$O(n)$

No sé si el segundo problema se puede resolver en tiempo polinómico. Creo que puedo calcular rápidamente un número de giro bien definido para cualquier polígono no simple (a menos que la unión de los bordes del polígono sea solo una ruta, en cuyo caso el polígono debe ser débilmente simple); mira mi respuesta a continuación. Sin embargo, el nuevo polígono de ejemplo anterior implica que el número 1 sin autocruzamiento y giro no implica débilmente simple.

Podemos determinar si un polígono dado es sencilla en tiempo comprobando cada par de bordes de intersección, o en tiempo utilizando un algoritmo de sweepline estándar, o incluso en tiempo usando el algoritmo de triangulación de Chazelle. (Si el polígono de entrada no es simple, cualquier algoritmo de triangulación arrojará una excepción, un bucle infinito o producirá una salida que no sea una triangulación válida). Pero ninguno de estos algoritmos resuelve los problemas que estoy preguntando. O ( n log n ) O ( n $O(n^2)$$O(n\log n)$$O(n)$

---

¹ Branko Grünbaum. Polígonos: Meister tenía razón y Poinsot estaba equivocado pero prevaleció . Beiträge zur Algebra und Geometrie 53 (1): 57–71, 2012.

² Ver, por ejemplo: Erik D. Demaine y Joseph O'Rourke. Algoritmos Geométricos Plegables: Vínculos, Origami, Poliedros . Cambridge University Press, 2007.

Parece que la primera pregunta tiene un algoritmo (aunque esto probablemente tampoco sea óptimo). Suponiendo que hay un cruce, la clave para encontrarlo parece ser que los bordes que se deben encontrar son los que se encuentran inmediatamente a cada lado del subruta común. Por lo tanto, observamos todos los pares de pares consecutivos de aristas. Hay un número cuadrático de estos. Si encontramos un par de pares de aristas con vértices y tal manera que las aristas y sean las mismas, entonces seguimos el subtrayecto común hasta el final e inspeccionamos las aristas que lo dejan. Si forman un cruce junto con y$O(n^3)$$abc$$def$$bc$$ef$$ab$$de$, entonces hemos terminado, de lo contrario pasamos al siguiente par. Seguir el subpath común es, como máximo, una operación de tiempo lineal, por lo que todo el algoritmo es .$O(n^3)$

Este análisis probablemente no sea ajustado, ya que el número de veces que se seguirá un subruta común de longitud lineal no es lineal en el número de pares de pares. Debería haber solo un número constante de esos. De manera similar, si la longitud del subpaso común más largo es constante, entonces estamos bien en términos de la cantidad de tiempo que sigue a los subpatros comunes. Esperaría que el peor de los casos surja cuando hay una sola ruta secundaria de longitud que es común a las rutas secundarias . Luego están las interacciones y en cada interacción se siguen los bordes . Entonces, aún así, el número de aristas que se siguen es$O(\sqrt{n})$$O(\sqrt{n})$$O(n)$o(n2)O(n2$O(\sqrt{n})$$o(n^2)$, y el límite lo proporciona el número de pares. Por lo tanto, supongo que el verdadero límite para este algoritmo es .$O(n^2)$

A sugerencia de Pat Morin, aquí está mi idea para calcular el número de giro. Lo siento si esto es un poco descuidado; Todavía estoy luchando contra los demonios de notación. Además, el comentario de Pat a la respuesta de Chris revela que he ignorado algunos casos importantes degenerados. Pero publicaré esto aquí de todos modos en caso de que otros lo encuentren útil.

Para cualquier índice , deje que denote el ángulo externo con signo en el vértice ; Este es el ángulo en sentido antihorario entre los rayos y , normalizado al rango . (Toda la aritmética de índice es implícitamente mod .) El número de giro de se define como Déjame llamar a un vértice un estímulo si el ángulo interno en$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$pipi0θiπ-πPPpi=pi+1Turn(P)Turn(P)=±1

$$Turn(P) = \frac{1}{2\pi} \sum_{i=0}^{n-1} \theta(p_i).$$ $p_i$$p_i$ es igual a . El ángulo externo en un espolón no está bien definido; podría ser o . En términos más generales, el número de giro de está bien definido si y solo si no tiene espuelas (y no tiene vértices repetidos ). No es difícil demostrar que es un número entero si está bien definido; en particular, si es un polígono simple.$0$$\theta_i$$\pi$$-\pi$$P$$P$$p_i=p_{i+1}$$Turn(P)$$Turn(P) = \pm 1$$P$

Ahora suponga que contiene una caminata de la forma , donde y el camino es la inversión de camino . Entonces es un estímulo; llama la raíz de . En este caso, permítame definir el ángulo externo en siguiente manera: (Pero qué si$P$$p\mathord\to r\mathord\leadsto s\mathord\leadsto r\mathord\to q$r ⇝ s $p\ne q$$r\mathord\leadsto s$$s\mathord\leadsto r$$s$$r$$s$$s$

$$\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$? Como Pat observa, esto realmente puede suceder. Probablemente hay algún tipo de forma recursiva para definir incluso en este caso, pero no sé qué es).$\tilde\theta(s)$

Si es débilmente simple, entonces hay una simple -gon arbitrariamente cerca de ; tet sea el vértice de más cercano a . Cuando acerca a , el ángulo interno en acerca a cero. No es difícil demostrar (por inducción en la longitud de ) que el ángulo externo aproxima a .$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)$

Si consiste completamente en una caminata seguida de su inversión, , entonces los ángulos externos en las espuelas y todavía no están bien definidos. Pero en este caso, creo que es débilmente simple si y solo si la caminata no se cruza a sí misma. (Hay casos más complejos en los que no puedo definir un número de giro modificado razonable, en particular, si el polígono va y viene a través de una sola caminata. Pero en todos estos casos, parece que el polígono es débilmente simple si y solo si no se cruza a sí mismo)$P$$r\mathord\leadsto s\mathord\leadsto r$$r$$s$$P$$r\mathord\leadsto s$

De lo contrario, si definimos para cualquier vértice no recto , ahora tenemos un número de giro bien definido , que debe ser si es débilmente simple.$\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$

Ya no estoy seguro de que se pueda calcular en tiempo lineal. La principal dificultad es que la caminata puede contener espuelas. El ingenuo algoritmo que encuentra la raíz de cada espolón por fuerza bruta en realidad lleva tiempo en el peor de los casos; considere un -gon que tiene un subcampo de longitud que simplemente alterna entre dos puntos.r⇝sΘ(n2)nΩ(n$\widetilde{Turn}(P)$$r\mathord\leadsto s$$\Theta(n^2)$$n$$\Omega(n)$