Geometria computacional

XenoCollide

Geometria Computacional é um ramo da Ciência da Computação que estuda algoritmos e estruturas de dados para a resolução computacional de problemas geométricos. Além disso, alguns problemas puramente geométricos surgem do estudo de algoritmos e, por isso, também são considerados parte da geometria computacional.

Os problemas em Geometria Computacional são tratados em termos de objetos geométricos elementares como pontos, retas, segmentos de reta, polígonos, etc. Em geral, o objetivo desta disciplina é resolver os problemas geométricos de forma eficiente, isto é, utilizando o menor número possível de operações simples sobre os elementos geométricos. A Geometria Computacional dá ênfase a complexidade computacional dos problemas e algoritmos estudados.

A Geometria Computacional emergiu de áreas de desenvolvimento e análise de algoritmos em meados da década de 1970. O primeiro uso do termo Geometria Computacional com este sentido ocorreu em 1975.[1]

A geometria computacional estuda tanto problemas geométricos clássicos, como também problemas motivados por diversas áreas da computação como Computação Gráfica, desenho assistido por computador (CAD/CAM), robótica, sistemas de informação geográfica, visão computacional, otimização combinatória, processamento de imagens, teoria dos grafos, desenho de circuitos integrados, aprendizagem de máquina etc.

Principais problemas

Muitos problemas de Geometria Computacional têm enunciados simples e várias soluções possíveis, desde as mais ingênuas até as mais eficientes. Alguns exemplos de problemas algorítmicos são listados abaixo.

• Fecho convexo: Dado um conjunto de pontos, determine o menor polígono/poliedro convexo contendo todos os pontos.
• Interseção de segmentos: Determinar as interseções de um dado conjunto de segmentos de retas.
• Triangulação de Delaunay
• Diagrama de Voronoi: Dado um conjunto de pontos, particione o espaço de acordo com qual ponto está mais próximo.
• Programação linear
• Par mais próximo: Dado um conjunto de pontos, determine o par de pontos com menor distância entre eles.
• Triangulação de polígonos: Dado um polígono, particione seu interior em triângulos.

Enquanto os problemas acimas possuem uma entrada fixa e uma saída construída em função da entrada, outros problemas geométricos são definidos em termos de consultas geométricas. Nestes problemas o objetivo é organizar os dados de modo a responder eficientemente múltiplas consultas. Alguns exemplos são:

• Busca de região: Preprocesse um conjunto de pontos de modo a eficientemente contar os pontos dentro de uma região de consulta.
• Localização de ponto: Dada uma partição do espaço em células, obtenha uma estrutura de dados que eficientemente diga em que região um ponto de consulta se encontra.
• Vizinho mais próximo: Preprocesse um conjunto de pontos de modo a eficientemente determinar o ponto mais próximo de um ponto de consulta.
• Traçado de raios: Dado um conjunto de objetos no espaço, produza uma estrutura de dados que eficientemente diga qual objeto que um raio de consulta intercepta primeiro.

Referências

1. Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. [S.l.]: Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3 

Ligações externas

• Biblioteca de Algoritmos em Geometria Computacional (CGAL)