Geometria Computacional
(Este curso foi substituido pelos cursos de algoritmos / processamento geometrico)
O propósito da Geometria Computacional é estudar problemas geométricos sob o ponto de vista algorítmico. Há um paralelo entre Geometria Computacional e Desenho Geométrico: em ambos o objetivo freqüentemente é obter novos elementos geométricos a partir de construções elementares. A diferença está em que, na Geometria Computacional, as figuras geométricas e construções correspondem a estruturas de dados e algoritmos, respectivamente. O problema de interesse, em geral, é o de efetuar uma determinada construção de modo a utilizar o menor número possível de passos elementares.
Nível
Mestrado
Este curso é parte do Programa Inter-institucional de CAD e Computação Gráfica (PiCG), uma realização conjunta do IMPA com a PUC-Rio.
Pré-requisitos
- Cálculo Vetorial
- Noções de algoritmos, estuturas de dados e programação
Programa
- Introdução
- Algoritmos geométricos: caracterização e classificação
- Tipos de problemas geométricos:
- decisão, seleção, construção;
- estático, on-line, dinâmico;
- one-shot, queries;
- Introdução à complexidade de algoritmos
- Algoritmos básicos
- Áreas de polígonos e poliedros
- Localização de pontos em polígonos e poliedros
- Volumes limitantes
- Fecho convexo
- Retângulos alinhados
- Retângulos não alinhados
- Círculos
- Pesquisa e seleção geométricas
- Estruturas de dados para pesquisa rápida baseada em volumes limitantes
- para pontos: quadtrees, k-d trees, r-trees
- para curvas: strip trees, arc trees, bbox-trees
- Queries
- Quais objetos estão num dado retângulo?
- Qual o objeto mais próximo de um dado ponto?
- Estruturas de dados para pesquisa rápida baseada em volumes limitantes
- Pesquisa e seleção com topologia
- Estruturas de dados para subdivisões planares
- Localização em mapas
- Interseção de segmentos de retas
- Detecção e identificação de interseções: caso geral, caso red-blue.
- Interpolação
- Dados discretos: diagramas de Voronoi -- construção e localização
- Dados contínuos: triangulações (Delaunay e outras), interpoladores
- Reconstrução de formas
- Redução de dados em curvas digitalizadas
- Ajuste de retas, círculos por mínimos quadrados
- Ajuste polinomial por partes
Referências básicas
- P. C. P. Carvalho e L. H. de Figueiredo, Introdução à Geometria Computational, 18° Colóquio Brasileiro de Matemática, IMPA, 1991.
- M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, 1997.
Outras referências
- F. P. Preparata e M. I. Shamos, Computational Geometry: an Introduction, Springer-Verlag, 1985.
- P. J. de Resende e J. Stolfi, Fundamentos de Geometria Computacional , IX Escola de Computação, SBC, 1994.
- J. O'Rourke, Computational Geometry in C, Cambridge University Press, 1994. Segunda edição, 1998.
- L. J. Guibas e J. Stolfi, Notes on Computational Geometry, Notas de aula, Stanford University, 1982.
- H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.
- K. Melhorn, Data Structures and Algorithms, Springer-Verlag, 1984.
- R. Sedgewick, Algorithms, Addison-Wesley, 1988.
- G. Toussaint (ed.), Computational Geometry, North-Holland, 1985.
- T. H. Cormen, C. E. Leiserson e R. L. Rivest, Introduction to Algorithms, MIT Press, 1990.
- D. Mount, Computational Geometry, Notas de curso, University of Maryland, 2002.
- C. Davis , Geometria Computacional para Sistemas de Informação Geográfica.
- J.-D. Boissonnat e M. Yvinec, Algorithmic Geometry, Cambridge University Press, 1998.
Surveys
- J. Erickson, Computational Geometry Pages.
- D. Eppstein, Geometry in Action.
- D. P. Dobkin, Computational Geometry: Then and Now, in: R. A. Earnshaw (ed.), Theoretical Foundations of Computer Graphics and CAD, Springer-Verlag, 1988.
- F. F. Yao, Computational Geometry, in: J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, MIT, 1990.