thumb|240px|O esqueleto reto, o processo de encolhimento que cria o esqueleto, e uma superfície tridimensional criada com ele.
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(n2 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 , ou simplesmente, 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 log2 n + r3/2 log r). No pior caso, r pode ser linear, e nesse caso o tempo pode ser simplificado para O(n3/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.
Categoria:Algoritmos Categoria:Geometria