# Esqueleto reto

Em geometria, um esqueleto reto é um método de representar um polígono por um esqueleto topológico. É similar ao eixo medial mas difere tendo o esqueleto formado apenas por segmentos de linhas retos, enquanto o eixo medial pode ter curvas parabólicas.
Esqueletos retos foram inicialmente definidos para polígonos simples por Aichholzer et al., e generalizados para grafo planar de linhas retas por Aichholzer and Aurenhammer.

## Definição

O esqueleto reto de um polígono é definido por um processo contínuo de encolhimento onde as arestas do polígono são movidas para dentro do polígono de forma paralela a elas a uma velocidade constante. Conforme as arestas movem, com os vértices das arestas movendo junto, a velocidades que dependem do angulo do vértice. Se um dos vértices que estão sendo movidos encontram uma aresta não adjacente, o polígono é dividido em dois pelo encontro, e o processo continua para cada parte. O esqueleto reto é o conjunto de curvas traçadas pelo movimento dos vértices no processo.
Por exemplo, parte (i) da ilustração mostra o esqueleto reto de um polígono. Parte (ii) mostra a sequencia de polígonos menores que são traçados durante o processo de encolhimento por mover as arestas.

## Algoritmos

O esqueleto reto pode ser computado por simulação do processo de encolhimento; algumas variantes desse algoritmo foram propostas, alterando as suposições feitas na entrada e nas estruturas de dados usadas para detectar as mudanças no polígono inicial conforme ele é encolhido.
* Aichholzer et al. mostrou como computar esqueletos retos para entradas arbitrárias de duas dimensões com tempo O(n$^2$ log n), ou em tempo O(nr log n), onde n é o número de vértices do polígono de entrada e r é o número de vértices côncavos. Um método mais simples com o mesmo tempo de execução é dado por Huber e Held, que argumentam que a abordagem deles tende a rodar em tempo quase-linear para muitas entradas.
* Usando estruturas de dados para o problema do par de pontos mais próximo, Eppstein e Erickson mostraram como construir esqueletos retos usando um número linear de atualizações numa estrutura de dados de par mais próximo. A estrutura de dados de par mais próximo baseada em quadtrees fornece um algoritmo com tempo O(nr + n log n), ou uma estrutura de dados significantemente mais complicada leva a melhores tempos como O(n$^{1+ε}$ + n$^{8/11+ε}$r$^{9/11+ε}$), ou simplesmenteO(n$^{17/11+ε}$), onde ε é uma constante qualquer maior que zero. Este continua sendo o melhor tempo de pior-caso conhecido para construção de esquelto reto com entradas sem restrições, mas é complicado e não foi implementado.
* Para polígonos simples, o problema de construir esqueleto reto é mais fácil. Cheng e Vigneron mostraram como computar o esqueleto reto de polígonos simples com n vértices, r tendo angulos maiores que Pi, com tempo O(n log$^2$ n + r$^{3/2}$ log r). No pior caso, r pode ser linear, e nesse caso o tempo pode ser simplificado para O(n$^{3/2}$ log n).
* Um polígono monótono com respeito a uma linha L é um polígono com a propriedade de que cada linha ortogonal a Lintersepta o polígono em um único intervalo. Quando a entrada é um polígono monótono, o esqueleto reto dele pode ser construído com tempo O(n log n).

## Aplicações

Cada ponto dentro do polígono de entrada pode ser passado para um espaço tridimensional usando o tempo em que o processo de encolhimento chega naquele ponto como coordenada z do ponto. A superfície tridimensional resultante terá a mesma altura nas arestas do polígono, e crescerá constantemente a partir delas com exceção dos pontos presentes no esqueleto reto, onde diferentes diferentes lados da superfície se encontram. Dessa forma, o esqueleto reto pode ser usado como um conjunto de linhas para a construção de um telhado, baseado nas paredes como polígono inicial. Parte (iii) da ilustração mostra uma superfície formada dessa forma partindo de um esqueleto reto.
Demaine, Demaine e Lubiw usaram o esqueleto reto como parte de uma técnica para dobrar papel de forma que um dado polígono pode ser cortado pelo esquelo reto, relacionado a desenvolvimento de problemas de origami.
Bagheri and Razzazi usam esqueletos retos para guiar um posicionamento de vértices em um algoritmo para desenhar grafos onde o grafo precisa estar dentro de um limite poligonal.
Como para outros tipos de esqueletos como eixo medial, o esqueleto reto pode ser usado para reduzir uma área bidimensional em uma representação simplificada unidimensional da área. Por exemplo, Haunert e Sester descreveram uma aplicação desse tipo para esqueletos retos em sistemas de informação geográfica, encontrando as linhas centrais de estradas.

## Dimensões superiores

Barequet et al. definiram uma versão de esqueletos retos para poliedros tridimensionais.

## References

* 1 2 3 Aichholzer, Oswin; Aurenhammer, Franz; Alberts, David; Gärtner, Bernd (1995). «A novel type of skeleton for polygons». Journal of Universal Computer Science. 1 (12): 752–761. MR 1392429 !CS1 manut: Nomes múltiplos: lista de autores (link)
* 1 2 Aichholzer, Oswin; Aurenhammer, Franz (1996). «Straight skeletons for general polygonal figures in the plane». Proc. 2nd Ann. Int. Conf. Computing and Combinatorics (COCOON '96). Lecture Notes in Computer Science, no. 1090, Springer-Verlag. pp. 117–126 !CS1 manut: Nomes múltiplos: lista de autores (link)
* ↑ Huber, Stefan; Held, Martin (2010). «Computing straight skeletons of planar straight-line graphs based on motorcycle graphs» (PDF). Proceedings of the 22nd Canadian Conference on Computational Geometry Huber, Stefan; Held, Martin (2011). «Theoretical and pratical results on straight skeletons of planar straight-line graphs». Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France. pp. 171–178 .
* ↑ Eppstein, David; Erickson, Jeff (1999). «Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions» (PDF). Discrete & Computational Geometry. 22 (4): 569–592. MR 1721026. doi:10.1007/PL00009479 !CS1 manut: Nomes múltiplos: lista de autores (link)
* ↑ Cheng, Siu-Wing; Vigneron, Antoine (2002). «Motorcycle graphs and straight skeletons» (PDF). Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 156–165 !CS1 manut: Nomes múltiplos: lista de autores (link)
* ↑ Das, Gautam K.; Mukhopadhyay, Asish; Nandy, Subhas C.; Patil, Sangameswar; Rao, S. V. (2010). «Computing the straight skeletons of a monotone polygon in O(n log n) time» (PDF). Proceedings of the 22nd Canadian Conference on Computational Geometry !CS1 manut: Nomes múltiplos: lista de autores (link)
* ↑ Bélanger, David (2000). «Designing Roofs of Buildings»
* ↑ Demaine, Erik D.; Demaine, Martin L.; Lubiw, Anna (1998). «Folding and cutting paper». Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG'98). Lecture Notes in Computer Science, no. 1763, Springer-Verlag. pp. 104–117. doi:10.1007/b75044 !CS1 manut: Nomes múltiplos: lista de autores (link)
* ↑ Bagheri, Alireza; Razzazi, Mohammadreza (2004). «Drawing free trees inside simple polygons using polygon skeleton». Computing and Informatics. 23 (3): 239–254. MR 2165282 !CS1 manut: Nomes múltiplos: lista de autores (link)
* ↑ Haunert, Jan-Henrik; Sester, Monika (2008). «Area collapse and road centerlines based on straight skeletons». Geoinformatica. 12 (2): 169–191. doi:10.1007/s10707-007-0028-x !CS1 manut: Nomes múltiplos: lista de autores (link)
* ↑ Raleigh, David Baring (2008). Straight Skeleton Survey Adjustment Of Road Centerlines From Gps Coarse Acquisition Data: A Case Study In Bolivia. Col: Masters thesis. [S.l.]: Ohio State University, Geodetic Science and Surveying
* ↑ Barequet, Gill; Eppstein, David; Goodrich, Michael T.; Vaxman, Amir (2008). «Straight skeletons of three-dimensional polyhedra». Proc. 16th European Symposium on Algorithms. Lecture Notes in Computer Science. 5193. Springer-Verlag. pp. 148–160. arXiv:0805.0022. doi:10.1007/978-3-540-87744-8_13 !CS1 manut: Nomes múltiplos: lista de autores (link)