O objetivo principal da pesquisa em geometria computacional combinatória é desenvolver algoritmos e estruturas de dados eficientes para resolver os problemas apresentados em termos de objetos geométricos básicos: pontos, segmentos de linha, polígonos, poliedros, etc.
alguns desses problemas parecem tão simples que não foram considerados problemas até o advento dos computadores. Considere, por exemplo, o problema do par mais próximo:
- Dados n pontos no plano, encontre os dois com a menor distância um do outro.
Um poderia calcular as distâncias entre todos os pares de pontos, dos quais existem n(n-1)/2, depois escolha o par com a menor distância. Este algoritmo de força bruta leva tempo O(n2), ou seja, seu tempo de execução é proporcional ao quadrado do número de pontos. Um resultado clássico na geometria computacional foi a formulação de um algoritmo que leva O(n log n). Algoritmos randomizados que levam o tempo esperado de O(n), assim como um algoritmo determinístico que leva o tempo de O(n log n), também foram descobertos.
Classes de problemasEditar
Os problemas centrais da geometria computacional podem ser classificados de diferentes maneiras, de acordo com vários critérios. As seguintes classes gerais podem ser distinguidas.
Problemas estáticosEditar
Nos problemas desta categoria, algumas entradas são dadas e a saída correspondente precisa ser construída ou encontrada. Alguns problemas fundamentais deste tipo são:
- Casco convexo: Dado um conjunto de pontos, encontre o menor poliedro/polígono convexo contendo todos os pontos.
- Interseção do segmento de linha: Encontrar as intersecções entre um dado conjunto de segmentos de linha.
- Triangulação Delunay
- Diagrama Voronoi: Dado um conjunto de pontos, divida o espaço de acordo com os pontos mais próximos aos pontos dados.
- Programação linear
- Par de pontos mais próximos: Dado um conjunto de pontos, encontre os dois com a menor distância um do outro.
- Par de pontos mais próximos
- Círculo maior vazio: Dado um conjunto de pontos, encontre um círculo maior com o seu centro dentro do seu casco convexo e não envolvendo nenhum deles.
- Euclidean caminho mais curto: Conecte dois pontos num espaço euclidiano (com obstáculos poliédricos) por um caminho mais curto.
- Triangulação poligonal: Dado um polígono, divida o seu interior em triângulos
- Geração Mesh
- Operações booleanas em polígonos
A complexidade computacional para esta classe de problemas é estimada pelo tempo e espaço (memória do computador) necessários para resolver uma determinada instância de problema.
Problemas de consulta geométricaEditar
Em problemas de consulta geométrica, comumente conhecidos como problemas de busca geométrica, a entrada consiste em duas partes: a parte do espaço de busca e a parte da consulta, que varia ao longo das instâncias do problema. O espaço de busca normalmente precisa ser pré-processado, de forma que múltiplas consultas possam ser respondidas eficientemente.
Alguns problemas fundamentais de busca geométrica são:
- Busca de intervalo: Pré-processar um conjunto de pontos, de forma a contar eficientemente o número de pontos dentro de uma região de busca.
- Localização dos pontos: Dada uma partição do espaço em células, produza uma estrutura de dados que diga eficientemente em qual célula um ponto de consulta está localizado.
- Vizinho mais próximo: Pré-processar um conjunto de pontos, a fim de encontrar eficientemente qual ponto está mais próximo de um ponto de consulta.
- Ray tracing: Dado um conjunto de objetos no espaço, produza uma estrutura de dados que diz eficientemente qual objeto um raio de consulta intercepta primeiro.
Se o espaço de busca é fixo, a complexidade computacional para esta classe de problemas é normalmente estimada por:
- o tempo e espaço necessários para construir a estrutura de dados a ser pesquisada em
- o tempo (e às vezes um espaço extra) para responder a consultas.
Para o caso em que o espaço de busca é permitido variar, veja “Problemas dinâmicos”.
Problemas dinâmicosEditar
Yet outra grande classe são os problemas dinâmicos, em que o objetivo é encontrar um algoritmo eficiente para encontrar uma solução repetidamente após cada modificação incremental dos dados de entrada (adição ou exclusão de elementos geométricos de entrada). Algoritmos para problemas deste tipo tipicamente envolvem estruturas de dados dinâmicas. Qualquer um dos problemas geométricos computacionais pode ser convertido em dinâmico, ao custo de um maior tempo de processamento. Por exemplo, o problema de busca de faixa pode ser convertido no problema de busca de faixa dinâmica, fornecendo a adição e/ou a exclusão dos pontos. O problema dinâmico do casco convexo é manter o controle do casco convexo, por exemplo, para o conjunto de pontos que muda dinamicamente, ou seja enquanto os pontos de entrada são inseridos ou apagados.
A complexidade computacional para esta classe de problemas é estimada por:
- o tempo e espaço necessários para construir a estrutura de dados a ser pesquisada em
- o tempo e espaço para modificar a estrutura de dados pesquisada após uma mudança incremental no espaço de pesquisa
- o tempo (e às vezes um espaço extra) para responder a uma consulta.
VariaçõesEditar
Alguns problemas podem ser tratados como pertencendo a qualquer uma das categorias, dependendo do contexto. Por exemplo, considere o seguinte problema.
- Ponto no polígono: Decida se um ponto está dentro ou fora de um determinado polígono.
Em muitas aplicações este problema é tratado como um disparo único, ou seja, pertencente à primeira classe. Por exemplo, em muitas aplicações de computação gráfica, um problema comum é encontrar qual área da tela é clicada por um ponteiro. No entanto, em algumas aplicações, o polígono em questão é invariante, enquanto que o ponto representa uma consulta. Por exemplo, o polígono de entrada pode representar uma fronteira de um país e um ponto é uma posição de uma aeronave, e o problema é determinar se a aeronave violou a fronteira. Finalmente, no exemplo anteriormente mencionado de computação gráfica, em aplicações CAD os dados de entrada alterados são frequentemente armazenados em estruturas de dados dinâmicas, que podem ser exploradas para acelerar as consultas de ponto em polígono.
Em alguns contextos de problemas de consulta há expectativas razoáveis sobre a seqüência das consultas, que podem ser exploradas tanto para estruturas de dados eficientes quanto para estimativas mais rigorosas de complexidade computacional. Por exemplo, em alguns casos é importante conhecer o pior caso para o tempo total de toda a sequência de N consultas, em vez de para uma única consulta. Veja também “análise amortizada”.