Poligonalización

En geometría computacional , una poligonización de un conjunto finito de puntos en el plano euclidiano es un polígono simple con los puntos dados como vértices. ^{[ 1 ]} Una poligonización también puede llamarse poligonización , ^{[ 2 ]} poligonización simple , ^{[ 3 ]} polígono hamiltoniano , ^{[ 4 ]} ciclo hamiltoniano sin cruces , ^{[ 5 ]} o ciclo generador de aristas rectas sin cruces . ^{[ 6 ]}

Cada conjunto de puntos que no se encuentra sobre una sola línea tiene al menos una poligonalización, la cual puede hallarse en tiempo polinomial. Para puntos en posición convexa , solo existe una, pero para otros conjuntos de puntos puede haber exponencialmente muchas. Encontrar una poligonalización óptima bajo varios criterios de optimización naturales es un problema difícil, que incluye como caso particular el problema del viajante . La complejidad de contar todas las poligonalizaciones sigue siendo desconocida.

Una poligonalización es un polígono simple que tiene como conjunto de vértices un conjunto dado de puntos en el plano euclidiano . Un polígono puede describirse mediante un orden cíclico en sus vértices, que están conectados en pares consecutivos por segmentos de línea, las aristas del polígono. Un polígono, definido de esta manera, es "simple" si los únicos puntos de intersección de estos segmentos de línea se encuentran en extremos comunes. ^{[ 2 ]}

Algunos autores solo consideran poligonalizaciones para puntos que están en posición general , es decir, que no hay tres en una línea. ^{[ 7 ]} Con esta suposición, el ángulo entre dos segmentos consecutivos del polígono no puede ser de 180°. Sin embargo, cuando se consideran conjuntos de puntos con colinealidades, generalmente se permite que sus poligonalizaciones tengan ángulos de 180° en algunos puntos. Cuando esto sucede, estos puntos se siguen considerando vértices, en lugar de estar dentro de aristas. ^{[ 8 ]}

Steinhaus (1964) observó que todo conjunto finito de puntos sin tres en una línea forma los vértices de un polígono simple. ^{[ 10 ]} Sin embargo, exigir que no haya tres en una línea es innecesariamente fuerte. En cambio, todo lo que se requiere para la existencia de una poligonalización (que permite ángulos de 180°) es que los puntos no se encuentren todos en una misma línea. Si no lo hacen, entonces tienen una poligonalización que se puede construir en tiempo polinomial . Una forma de construir una poligonalización es elegir cualquier punto${\displaystyle q}$en la envoltura convexa de${\displaystyle P}$(no necesariamente uno de los puntos dados). Luego, ordenando radialmente los puntos alrededor de${\displaystyle q}$(resolviendo los empates por distancia desde q) produce el ordenamiento cíclico de un polígono en forma de estrella a través de todos los puntos dados, con${\displaystyle q}$en su núcleo. ^{[ 7 ]} La misma idea de ordenar puntos radialmente alrededor de un punto central se utiliza en algunas versiones del algoritmo de envolvente convexa de escaneo de Graham , y se puede realizar en${\displaystyle O(n\log n)}$tiempo. ^{[ 11 ]} Las poligonalizaciones que evitan los ángulos de 180° no siempre existen. Por ejemplo, para cuadrículas cuadradas de 3 × 3 y 5 × 5 , todas las poligonalizaciones utilizan ángulos de 180°. ^{[ 9 ]}

Además de las poligonalizaciones en forma de estrella, todo conjunto de puntos no colineales tiene una poligonalización que es un polígono monótono . Esto significa que, con respecto a alguna línea recta (que puede tomarse como la${\displaystyle x}$-eje) cada línea perpendicular a la línea de referencia interseca el polígono en un solo intervalo, o no lo interseca en absoluto. Una construcción de Grünbaum (1994) comienza ordenando los puntos por su${\displaystyle x}$-coordenadas, y trazando una línea que pase por los dos puntos extremos. Dado que los puntos no están todos alineados, al menos uno de los dos semiplanos abiertos delimitados por esta línea debe ser no vacío. Grünbaum forma dos cadenas poligonales monótonas que conectan los puntos extremos mediante subsecuencias ordenadas de los puntos: una para los puntos en este semiplano abierto no vacío y la otra para los puntos restantes. Su unión es el polígono monótono deseado. Tras el paso de ordenación, el resto de la construcción puede realizarse en tiempo lineal . ^{[ 4 ]}

Es NP-completo determinar si un conjunto de puntos tiene una poligonalización utilizando solo aristas paralelas a los ejes. ^{[ 12 ]} Sin embargo, las poligonalizaciones con la restricción adicional de que giren a la derecha en cada vértice, si existen, se determinan de forma única. Cada línea paralela a los ejes que pasa por un punto debe pasar por un número par de puntos, y esta poligonalización debe conectar pares alternos de puntos en esta línea. La poligonalización se puede encontrar en el tiempo${\displaystyle O(n\log n)}$agrupando los puntos por coordenadas iguales y ordenando cada grupo por la otra coordenada. ^{[ 13 ]} Para cualquier conjunto de puntos, como máximo una rotación puede tener una poligonalización de esta forma, y ​​esta rotación puede hallarse de nuevo en tiempo polinomial. ^{[ 14 ]}

Los problemas de encontrar una poligonalización óptima (para diversos criterios de optimización) suelen ser computacionalmente inviables. Por ejemplo, la solución al problema del viajante , para los puntos dados, no tiene cruces. Por lo tanto, siempre es una poligonalización, la poligonalización con el perímetro mínimo . ^{[ 15 ]} Es NP-difícil de encontrar. De manera similar, encontrar la poligonalización simple con área mínima o máxima es NP-difícil, ^{[ 3 ]} y ha sido objeto de algunos esfuerzos computacionales. ^{[ 16 ] [ 17 ]} El área máxima siempre es mayor que la mitad del área de la envoltura convexa , lo que da una razón de aproximación de 2. ^{[ 18 ]} La complejidad exacta de la poligonalización simple con perímetro máximo, y la existencia de una razón de aproximación constante para este problema, siguen siendo desconocidas. ^{[ 5 ]} La poligonalización que minimiza la longitud de su arista más larga también es NP-difícil de encontrar, y difícil de aproximar a una razón de aproximación mejor que${\displaystyle {\sqrt {3}}}$; no se conoce ninguna aproximación de factor constante. ^{[ 19 ]}

Una solución no óptima al problema del viajante puede tener cruces, pero es posible eliminarlos todos mediante pasos de optimización local que reducen la longitud total. Utilizando pasos que también eliminan cruces en cada paso, esto se puede hacer en tiempo polinomial ^{[ 20 ]} , pero sin esta restricción existen secuencias de optimización local que utilizan un número exponencial de pasos ^{[ 21 ] .}

El recorrido bitónico más corto (el polígono monótono de perímetro mínimo que pasa por los puntos dados) es siempre una poligonalización y se puede encontrar en tiempo polinomial. ^{[ 22 ]}

El problema de contar todas las poligonalizaciones de un conjunto de puntos dado pertenece a #P , la clase de problemas de conteo asociados con problemas de decisión en NP . Sin embargo, se desconoce si es #P-completo o, de no ser así, cuál podría ser su complejidad computacional. ^{[ 23 ] [ 24 ]} Un conjunto de puntos tiene exactamente una poligonalización si y solo si está en posición convexa . ^{[ 1 ]} Existen conjuntos de${\displaystyle n}$puntos para los cuales el número de poligonizaciones es tan grande como${\displaystyle 4.64^{n}}$, ^{[ 25 ]} y cada conjunto de${\displaystyle n}$puntos tiene como máximo${\displaystyle 54.6^{n}}$poligonalizaciones. ^{[ 6 ]}

Los métodos que aplican el teorema del separador planar a triangulaciones etiquetadas de los puntos se pueden utilizar para contar todas las poligonalizaciones de un conjunto de${\displaystyle n}$puntos en tiempo subexponencial,${\displaystyle n^{O({\sqrt {n}})}}$. ^{[ 26 ]} La programación dinámica se puede utilizar para contar todas las poligonalizaciones monótonas en tiempo polinomial, y los resultados de este cálculo se pueden utilizar para generar una poligonalización monótona aleatoria. ^{[ 27 ]}

Se desconoce si es posible que el sistema de todas las poligonalizaciones forme un espacio de estados conexo bajo movimientos locales que modifiquen un número limitado de aristas de las poligonalizaciones. Si esto fuera posible, podría utilizarse como parte de un algoritmo para generar todas las poligonalizaciones, aplicando un recorrido de grafo al espacio de estados. Para este problema, no basta con considerar las operaciones de volteo que eliminan dos aristas de una poligonalización y las reemplazan por otras dos, ni las operaciones de volteo VE que eliminan tres aristas, dos de las cuales comparten un vértice, y las reemplazan por otras tres. Existen poligonalizaciones para las que no es posible realizar ninguna operación de volteo ni de volteo VE, aunque el mismo conjunto de puntos tenga otras poligonalizaciones. ^{[ 28 ]}

Los polígonos envolventes , polígonos débilmente simples que usan cada punto dado una o más veces como vértice, incluyen todas las poligonalizaciones y están conectados por movimientos locales. ^{[ 2 ]} Otra clase más general de polígonos, los polígonos circundantes , son polígonos simples que tienen algunos de los puntos dados como vértices y encierran todos los puntos. Están conectados localmente de nuevo y se pueden listar en tiempo polinomial por polígono. El algoritmo construye un árbol de polígonos, con la envoltura convexa como su raíz y con el padre de cada otro polígono circundante obtenido al eliminar un vértice (demostrado que es posible aplicando el teorema de las dos orejas al exterior del polígono). Luego aplica un algoritmo de búsqueda inversa a este árbol para listar los polígonos. Como consecuencia de este método, todas las poligonalizaciones se pueden listar en tiempo exponencial (${\displaystyle 2^{O(n)}}$para${\displaystyle n}$puntos) y espacio polinomial . ^{[ 29 ]}

Los rompecabezas clásicos de unir los puntos implican conectar puntos en secuencia para formar una figura inesperada, a menudo sin cruces. ^{[ 30 ]} El problema del viajante y sus variantes tienen muchas aplicaciones. ^{[ 31 ]} La poligonalización también tiene aplicaciones en la reconstrucción de líneas de contorno a partir de puntos de datos dispersos y en el trazado de límites en el análisis de imágenes . ^{[ 32 ]}

• Teorema de Denjoy-Riesz , sobre conjuntos de infinitos puntos que pueden conectarse mediante un arco de Jordan.