Geometria Computacional - 2010

Professores

Guilherme D. da Fonseca

Claudio Esperança

Tarefas

• Lista de exercícios
• Lista de exercícios de aproximação geométrica

Tópicos

• Fecho Convexo: Algoritmos de Jarvis [2], Graham [1,2] e Chan [2].
• Dualidade Geométrica [1,2].
• Programação Linear: Algoritmos randomizados incrementais [1,2], algoritmo randomizado de Seidel [1,2], análise de trás para frente [1,2].
• Arranjo de Retas: DCEL [1], construção incremental [1,2], teorema da vizinhança (zone's theorem) [1,2], teorema de Euler [2,6].
• Aulas do Cláudio falando de tópicos como: Linha de varredura, triangulação, Diagrama de Voronoi, Localização de Pontos, Busca de região...
• Aproximação geométrica: grades e diâmetro [12,3], minimum k-enclosing ball[12,3], Quadtrees [12,3], decomposição em pares bem separados (WSPD) [12,2,3], spanners [12,2,3].

Referências

1. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, 1997. Segunda edição revisada em 2000.
2. Notas de aula do David Mount, que seguem paralelamente ao livro acima.
3. Notas de aproximação geométrica do Sariel Har-Peled.
4. Notas de aula do Luiz Henrique e Paulo Cezar.
5. P. C. P. Carvalho e L. H. de Figueiredo, Introdução à Geometria Computational, 18° Colóquio Brasileiro de Matemática, IMPA, 1991.
6. J.-D. Boissonnat e M. Yvinec, Algorithmic Geometry, Cambridge University Press, 1998.
7. Celina Miraglia Herrera de Figueiredo, Guilherme Dias da Fonseca, Manoel José Machado Soares Lemos, Vinícius Gusmão Pereira de Sá, Introdução aos Algoritmos Randomizados, 26° Colóquio Brasileiro de Matemática, IMPA, 2007.
8. Transparências do Cláudio Esperança.
9. Outras referências...
10. Ainda outras referências...
11. Links interessantes selecionados pelo Luiz Henrique.
12. Slides de aproximação geométrica.