miniatura|upright=1.35|16 poligonalizaciones de un conjunto de seis puntos
En geometría computacional, una poligonalización de un conjunto finito de puntos del plano euclidiano es un polígono simple cuyos vértices son precisamente los puntos dados.
Una poligonalización también puede denominarse poligonización, poligonización simple, polígono hamiltoniano, ciclo hamiltoniano sin cruces, o ciclo que abarca aristas rectas sin cruces.
Todo conjunto de puntos que no esté contenido en una única recta posee al menos una poligonalización, la cual puede encontrarse en tiempo polinómico. Para los puntos en posición convexa existe una sola poligonalización, mientras que para otros conjuntos pueden existir exponencialmente muchas. Encontrar una poligonalización óptima según diversos criterios naturales de optimización constituye un problema difícil, e incluye como caso particular el problema del viajante. La complejidad computacional de contar todas las poligonalizaciones sigue siendo desconocida.
Definición
Una poligonalización es un polígono simple que tiene como conjunto de vértices un conjunto dado de puntos del plano euclidiano. Un polígono puede describirse mediante un orden cíclico de sus vértices, unidos en pares consecutivos mediante segmentos de recta que constituyen sus lados. Un polígono definido de esta manera es «simple» cuando los únicos puntos de intersección entre dichos segmentos son sus extremos comunes.
Algunos autores consideran únicamente poligonalizaciones para conjuntos de puntos en posición general, es decir, en los que no existen tres puntos colineales. Bajo esta hipótesis, el ángulo entre dos lados consecutivos del polígono nunca puede ser de 180°. Sin embargo, cuando se consideran conjuntos de puntos con colinealidades, generalmente se permite que las poligonalizaciones presenten ángulos de 180° en algunos vértices. En estos casos, dichos puntos siguen considerándose vértices y no puntos interiores de un lado.
Existencia
miniatura|Poligonalizaciones de una cuadrícula de . Los ángulos de 180° visibles en cada polígono son necesarios: para una cuadrícula de este tamaño, todas las poligonalizaciones contienen un ángulo de 180°.
observó que todo conjunto finito de puntos sin tres colineales constituye el conjunto de vértices de un polígono simple. Sin embargo, exigir que no existan tres puntos alineados resulta una condición más fuerte de lo necesario. En realidad, basta con que los puntos no estén todos sobre una misma recta para garantizar la existencia de una poligonalización (permitiendo ángulos de 180°). En tal caso, puede construirse en tiempo polinómico. Una forma de construir una poligonalización consiste en elegir cualquier punto perteneciente a la envolvente convexa de (sin que necesariamente sea uno de los puntos dados). Luego, al ordenar radialmente los puntos alrededor de (deshaciendo empates mediante la distancia a ) se obtiene el orden cíclico de un polígono estrellado que pasa por todos los puntos dados y cuyo núcleo contiene a . Esta misma idea de ordenar radialmente los puntos alrededor de un punto central también se utiliza en algunas versiones del algoritmo de escaneo de Graham para calcular la envolvente convexa y puede realizarse en tiempo . No siempre existen poligonalizaciones que eviten ángulos de 180°. Por ejemplo, en las cuadrículas cuadradas de y , todas las poligonalizaciones contienen ángulos de 180°.
Además de las poligonalizaciones estrelladas, todo conjunto no colineal de puntos admite una poligonalización que es un polígono monótono. Esto significa que, con respecto a una determinada recta (que puede tomarse como el eje ), toda recta perpendicular a la recta de referencia intersecta el polígono en un único intervalo, o no lo intersecta en absoluto. La construcción propuesta por comienza ordenando los puntos según sus coordenadas y trazando una recta que pasa por los dos puntos extremos. Como los puntos no son todos colineales, al menos uno de los dos semiespacios abiertos delimitados por dicha recta debe ser no vacío. Grünbaum construye entonces dos cadenas poligonales monótonas que conectan los puntos extremos recorriendo subsecuencias ordenadas de los puntos: una para los puntos pertenecientes al semiplano abierto no vacío y otra para los puntos restantes. La unión de ambas cadenas constituye el polígono monótono buscado. Tras la etapa de ordenamiento, el resto de la construcción puede realizarse en tiempo lineal.
Determinar si un conjunto de puntos admite una poligonalización cuyos lados sean únicamente paralelos a los ejes es un problema NP-completo. Sin embargo, las poligonalizaciones que, además, realizan un giro recto en cada vértice, cuando existen, están determinadas de manera única. Cada recta paralela a los ejes que pasa por un punto debe contener un número par de puntos, y la poligonalización debe conectar pares alternados de puntos sobre dicha recta. Puede encontrarse en tiempo agrupando los puntos con la misma coordenada y ordenando cada grupo según la otra coordenada. Para cualquier conjunto de puntos, como máximo una rotación admite una poligonalización de este tipo, y dicha rotación también puede encontrarse en tiempo polinómico.
Optimización
Los problemas de encontrar una poligonalización óptima (según distintos criterios de optimalidad) suelen ser computacionalmente intratables. Por ejemplo, la solución del problema del viajante para un conjunto dado de puntos nunca contiene cruces. En consecuencia, siempre constituye una poligonalización: aquella cuyo perímetro es mínimo. Hallarla es un problema NP-hard. Del mismo modo, encontrar la poligonalización simple de área mínima o máxima también es NP-hard, y ha sido objeto de numerosos estudios computacionales. El área máxima siempre supera la mitad del área de la envolvente convexa, lo que proporciona una razón de aproximación de 2. La complejidad exacta de encontrar la poligonalización simple de perímetro máximo, así como la existencia de una razón de aproximación constante para este problema, siguen siendo desconocidas. La poligonalización que minimiza la longitud de su lado más largo también es NP-hard y resulta difícil aproximarla con un factor mejor que ; actualmente no se conoce ninguna aproximación con factor constante.
Una solución no óptima del problema del viajante puede contener cruces, pero es posible eliminarlos mediante pasos de optimización local que reducen la longitud total del recorrido. Si cada paso también elimina los cruces, este procedimiento puede realizarse en tiempo polinómico.Sin esta restricción, existen secuencias de optimización local que requieren un número exponencial de pasos.
El recorrido bitónico más corto (es decir, el polígono monótono de perímetro mínimo que pasa por los puntos dados) siempre constituye una poligonalización y puede encontrarse en tiempo polinómico. Conteo
El problema de contar todas las poligonalizaciones de un conjunto dado de puntos pertenece a #P, la clase de problemas de conteo asociada a los problemas de decisión de NP. Sin embargo, se desconoce si es #P-completo o, en caso contrario, cuál es exactamente su complejidad computacional. Un conjunto de puntos posee exactamente una poligonalización si y solo si se encuentra en posición convexa.Existen conjuntos de puntos cuyo número de poligonalizaciones alcanza , mientras que cualquier conjunto de puntos posee como máximo poligonalizaciones.
Los métodos que aplican el teorema del separador planar a las triangulaciones etiquetadas de los puntos permiten contar todas las poligonalizaciones de un conjunto de puntos en tiempo subexponencial, . La programación dinámica permite contar todas las poligonalizaciones monótonas en tiempo polinómico, y los resultados de este cálculo pueden utilizarse posteriormente para generar una poligonalización monótona aleatoria.
Generación
miniatura|Un polígono que no puede transformarse en ningún otro polígono sobre el mismo conjunto de puntos mediante flips o VE-flips.
Se desconoce si el conjunto de todas las poligonalizaciones forma un espacio de estados conexo mediante movimientos locales que modifican un número acotado de lados del polígono. Si ello fuera posible, podría emplearse como parte de un algoritmo para generar todas las poligonalizaciones, aplicando un recorrido de grafos sobre dicho espacio de estados. Para este problema no basta considerar únicamente los flips, que eliminan dos lados de una poligonalización y los sustituyen por otros dos, ni los VE-flips, que eliminan tres lados —dos de ellos incidentes en un mismo vértice— y los reemplazan por otros tres. Existen poligonalizaciones para las cuales no es posible realizar ningún flip ni ningún VE-flip, aunque el mismo conjunto de puntos admita otras poligonalizaciones.
Los polygonal wraps, es decir, polígonos débilmente simples que utilizan cada punto dado una o más veces como vértice, incluyen todas las poligonalizaciones y forman un espacio conexo mediante movimientos locales. Otra clase más general corresponde a los surrounding polygons, que son polígonos simples cuyos vértices incluyen algunos de los puntos dados y que encierran a todos los puntos del conjunto. Estos polígonos también forman un espacio localmente conexo y pueden enumerarse en tiempo polinómico por polígono. El algoritmo construye un árbol de polígonos cuya raíz es la envolvente convexa, y donde el padre de cada polígono circundante se obtiene eliminando uno de sus vértices (lo que puede demostrarse aplicando el teorema de las dos orejas al exterior del polígono). Posteriormente aplica un algoritmo de búsqueda inversa sobre dicho árbol para enumerar todos los polígonos. Como consecuencia, todas las poligonalizaciones pueden enumerarse en tiempo exponencial ( para puntos) utilizando espacio polinómico. Aplicaciones
Los clásicos pasatiempos de une los puntos consisten en conectar una secuencia de puntos para formar una figura inesperada, generalmente evitando que los segmentos se crucen. El problema del viajante y sus variantes poseen numerosas aplicaciones prácticas. Asimismo, las poligonalizaciones tienen aplicaciones en la reconstrucción de curvas de nivel a partir de puntos de datos dispersos y en el seguimiento de contornos dentro del análisis de imágenes.
Referencias
Categoría:Polígonos Categoría:Geometría computacional