Geometria Computacional - 2008

Professores

Guilherme D. da Fonseca

Celina M. H. de Figueiredo

Horário e local

2^a, 5^a: 13:00-15:00, na sala H304-B.
A primeira aula será no dia 9/6 e a última no dia 28/8, com provas nos dias 17/7 e 4/9.

Tópicos

• Fecho Convexo: Algoritmos de Jarvis [2], Graham [1,2] e Chan [2].
• Linha de varredura: Interseção de segmentos [1,2], triangulação de polígonos [1,2].
• Arranjo de Retas: DCEL [1], construção incremental [1,2], teorema da vizinhança (zone's theorem) [1,2], arranjo de hiperplanos [6], teorema de Euler [2,6].
• Dualidade Geométrica: Corte do sanduiche de presunto [2], co-linearidade e outras aplicações [1,2].
• Estruturas de Dados Cinéticas: Torneio cinético [tese], sequências de Davemport-Schinzel [survey], k-ésimo nível [artigo].
• Programação Linear: Algoritmos randomizados incrementais [1,2], algoritmo randomizado de Seidel [1,2], análise de trás para frente [1,2].
• Localização de Pontos: Refinamento de triangulação de Kirkpatrick [2].
• Diagrama de Voronoi e triangulação de Delaunay: Algoritmo de Fortune [1,2], propriedades [1,2], curse of dimensionality.
• Busca de região: kd-trees [1,2], range-trees [1,2] e busca de semi-espaços e simplexos.
• Aproximação geométrica: grades e par mais próximo [7,3], minimum k-enclosing disk[3], Quadtrees [3], busca de região aproximada, decomposição em pares bem separados (WSPD) [2,3], spanners [2,3], dimensão de VC[2,3], epsilon approximations [2,3] e epsilon nets [2,3].

Avaliação

• 30% prova escrita no dia 17/7 (pseudo-prova)
• 40% trabalho teórico ou prático para entrega no dia 1/9
• 30% prova escrita no dia 4/9 (solução e pseudo-prova)

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.