Esqueleto recto

En geometría , un esqueleto recto es un método para representar un polígono mediante un esqueleto topológico . Es similar en algunos aspectos al eje medial , pero se diferencia en que el esqueleto está compuesto por segmentos de línea recta, mientras que el eje medial de un polígono puede incluir curvas parabólicas. Sin embargo, ambos son homotópicamente equivalentes al polígono subyacente. ^{[ 1 ]}

Los esqueletos rectos fueron definidos por primera vez para polígonos simples por Aichholzer et al. (1995) ^{[ 2 ]} y generalizados a grafos de líneas rectas planas (PSLG) por Aichholzer y Aurenhammer (1996) ^{[ 3 ]} . En su interpretación como proyección de superficies de techo, ya han sido ampliamente discutidos por G.A. Peschka ( 1877 ) ^{[ 4 ]} . 

El esqueleto recto de un polígono se define mediante un proceso continuo de contracción en el que las aristas se mueven hacia adentro paralelamente a sí mismas a una velocidad constante. A medida que las aristas se mueven de esta manera, los vértices donde se encuentran pares de aristas también se mueven, a velocidades que dependen del ángulo del vértice. Si uno de estos vértices en movimiento colisiona con una arista no adyacente, el polígono se divide en dos debido a la colisión, y el proceso continúa en cada parte. El esqueleto recto es el conjunto de curvas trazadas por los vértices en movimiento durante este proceso. En la ilustración, la figura superior muestra el proceso de contracción y la figura central representa el esqueleto recto en azul.

El esqueleto recto se puede calcular simulando el proceso de contracción mediante el cual se define; se han propuesto varios algoritmos variantes para calcularlo, que difieren en las suposiciones que hacen sobre la entrada y en las estructuras de datos que utilizan para detectar cambios combinatorios en el polígono de entrada a medida que se contrae.

Los siguientes algoritmos consideran una entrada que forma un polígono, un polígono con agujeros o un PSLG. Para una entrada poligonal, denotamos el número de vértices por n y el número de vértices reflejos (cóncavos, es decir, con un ángulo mayor que π ) por r . Si la entrada es un PSLG, entonces consideramos la estructura inicial del frente de onda, que forma un conjunto de polígonos, y nuevamente denotamos por n el número de vértices y por r el número de vértices reflejos con respecto a la dirección de propagación. La mayoría de los algoritmos aquí enumerados están diseñados y analizados en el modelo de computación RAM real .

• Aichholzer et al. ^{[ 2 ] [ 3 ]} mostraron cómo calcular esqueletos rectos de PSLG en tiempo O( n ³  log n ), o más precisamente tiempo O(( n ² + f ) log n ), donde n es el número de vértices del polígono de entrada y f es el número de eventos de volteo durante la construcción. La mejor cota conocida para f es O( n ³ ).   
• Huber y Held ( 2010 , 2011 ) presentan un algoritmo con un tiempo de ejecución en el peor de los casos de O( ^nr log  n  ), o simplemente O( n² log n) , argumentando que su enfoque probablemente se ejecute en un tiempo casi lineal para muchas entradas. ^{[ 5 ] [ 6 ]}   
• Petr Felkel y Štěpán Obdržálek diseñaron un algoritmo para polígonos simples que supuestamente tiene una eficiencia de O( nr + n log r ). ^{[ 7 ] [ 8 ]} Sin embargo, se ha demostrado que su algoritmo es incorrecto. ^{[ 9 ] [ 10 ]}
• Al utilizar estructuras de datos para el problema del par más cercano bicromático , Eppstein y Erickson demostraron cómo construir problemas de esqueletos rectos utilizando un número lineal de actualizaciones de la estructura de datos del par más cercano. Una estructura de datos del par más cercano basada en quadtrees proporciona un algoritmo de tiempo O( nr  + n log n ), o una estructura de datos significativamente más compleja conduce a la mejor cota de tiempo asintótica O( n ^{1 + ε} + n ^{8/11 + ε} r ^{9/11 + ε} ) , o más simplemente O( n ^{17/11 + ε} ) , donde ε es cualquier constante mayor que cero. ^{[ 11 ]} Esta sigue siendo la mejor cota de tiempo en el peor de los casos conocida para la construcción de esqueletos rectos con entradas no restringidas, pero es compleja y no se ha implementado.   
• Para polígonos simples en posición general , el problema de la construcción de esqueletos rectos es más fácil. Cheng, Mencel y Vigneron mostraron cómo calcular el esqueleto recto de polígonos simples en tiempo O( n log n log r + r ^{4/3 + ε} ). ^{[ 12 ]} En el peor de los casos, r puede ser del orden de n , en cuyo caso este límite de tiempo puede simplificarse a O( n ^4/3+ε ). Si los vértices del polígono de entrada tienen coordenadas racionales de O(log n) bits, su algoritmo puede mejorarse para ejecutarse en tiempo O( n  log n ), incluso si el polígono de entrada no está en posición general . 
• Un polígono monótono con respecto a una línea L es un polígono cuya propiedad es que toda línea ortogonal a L lo interseca en un único intervalo. Cuando la entrada es un polígono monótono, su esqueleto recto se puede construir en tiempo O( n  log ² n ). ^{[ 13 ]} 

Cada punto dentro del polígono de entrada puede elevarse al espacio tridimensional utilizando el tiempo en el que el proceso de contracción alcanza ese punto como la coordenada z del punto. La superficie tridimensional resultante tiene una altura constante en los bordes del polígono y se eleva con una pendiente constante desde ellos, excepto en los puntos del propio esqueleto recto, donde se encuentran parches de superficie en diferentes ángulos. De esta manera, el esqueleto recto puede utilizarse como el conjunto de líneas de cumbrera de un tejado de un edificio, basándose en paredes con la forma del polígono inicial. ^{[ 2 ] [ 14 ]} La figura inferior de la ilustración muestra una superficie formada a partir del esqueleto recto de esta manera.

Demaine, Demaine y Lubiw utilizaron el esqueleto recto como parte de una técnica para doblar una hoja de papel de manera que se pueda cortar un polígono dado con un solo corte recto (el teorema de doblar y cortar ), y problemas de diseño de origami relacionados . ^{[ 15 ]}

Barequet et al. utilizan esqueletos rectos en un algoritmo para encontrar una superficie tridimensional que interpola entre dos cadenas poligonales dadas . ^{[ 16 ]}

Tănase y Veltkamp proponen descomponer polígonos cóncavos en uniones de regiones convexas utilizando esqueletos rectos, como paso de preprocesamiento para la coincidencia de formas en el procesamiento de imágenes. ^{[ 17 ]}

Bagheri y Razzazi utilizan esqueletos rectos para guiar la colocación de vértices en un algoritmo de dibujo de grafos en el que el dibujo del grafo está restringido a estar dentro de un límite poligonal. ^{[ 18 ]}

El esqueleto recto también puede utilizarse para construir una curva desplazada de un polígono, con esquinas biseladas , de forma análoga a la construcción de una curva desplazada con esquinas redondeadas formadas a partir del eje medial. Tomoeda y Sugihara aplican esta idea en el diseño de señalización, visible desde ángulos amplios, con una apariencia ilusoria de profundidad. ^{[ 19 ]} De manera similar, Asente y Carr utilizan esqueletos rectos para diseñar degradados de color que coinciden con los contornos de las letras u otras formas. ^{[ 20 ]}

Al igual que con otros tipos de esqueletos, como el eje medial , el esqueleto recto puede utilizarse para reducir un área bidimensional a una representación unidimensional simplificada. Por ejemplo, Haunert y Sester describen una aplicación de este tipo para esqueletos rectos en sistemas de información geográfica , en la determinación de los ejes centrales de las carreteras. ^{[ 21 ] [ 22 ]}

En la generación de mallas mediante el método de elementos finitos (MEF) , se han utilizado los conceptos de esqueleto recto y contracción basada en capas para descomponer dominios geométricos complejos para el modelado hidrodinámico y de aguas poco profundas. Al analizar las capas de propagación del frente de onda, los algoritmos pueden transformar automáticamente mallas triangulares no estructuradas en cuadrículas cuadriláteras alineadas y de elementos mixtos, ajustándose a una función de tamaño geométrico subyacente. ^{[ 23 ]}

Todo árbol sin vértices de grado dos puede realizarse como el esqueleto recto de un polígono convexo . ^{[ 24 ]} La envoltura convexa de la forma del techo correspondiente a este esqueleto recto forma una realización de Steinitz del grafo de Halin formado a partir del árbol conectando sus hojas en un ciclo.

Barequet et al. definieron una versión de esqueletos rectos para poliedros tridimensionales , describieron algoritmos para calcularla y analizaron su complejidad en varios tipos diferentes de poliedros. ^{[ 25 ]}

Huber et al. investigaron espacios métricos bajo los cuales coinciden los diagramas de Voronoi y los esqueletos rectos correspondientes. Para dos dimensiones, la caracterización de dichos espacios métricos es completa. Para dimensiones superiores, este método puede interpretarse como una generalización de esqueletos rectos de ciertas formas de entrada a dimensiones arbitrarias mediante diagramas de Voronoi. ^{[ 26 ]}

• Erickson, Jeff. "Esqueleto recto de un polígono simple" .
• Esqueleto recto 2D en CGAL , la biblioteca de algoritmos de geometría computacional.
• Esqueleto recto para polígono con agujeros. Constructor de esqueleto recto implementado en Java.
• Amit Parnerkar, Sarnath Ramnath. "Diseño de un algoritmo eficiente para encontrar el esqueleto recto de un polígono simple en O(n log n) " .
• STALGO : "STALGO es un paquete de software C++ de nivel industrial para calcular esqueletos rectos y curvas de inglete desplazadas." Por Stefan Huber.