Programação das aulas
Primeiro semestre de 2022
Março
Abril
Maio
- 2 de maio (Aula 11):
- Triangulações ângulo-ótimas e legais
- Grafo de Delaunay e triangulações de Delaunay
Slides: [pdf]
Leitura recomendada: secs 9.1 e 9.2 do livro de de Berg e outros.
- 4 de maio (Aula 12):
- Algoritmos para construir triangulação de Delaunay
Slides: [pdf]
Leitura recomendada: sec 9.3 do livro de de Berg e outros.
- 9 de maio (Aula 13):
Slides: [pdf]
Leitura recomendada: sec 7.4 do livro do O'Rourke.
- 11 de maio (Aula 14):
- Par de pontos mais próximos: linha de varredura e um algoritmo aleatorizado
- Quarto projeto
Slides: [pdf]
Leitura recomendada: sec 13.7 do livro de Kleinberg e Tardos
(Algorithm Design).
- 16 de maio (Aula 15):
- Partições convexas
- Algoritmo de Hertel e Mehlhorn
- Ideia do algoritmo de Keil e Snoeyink
Slides: [pdf]
Leitura recomendada: sec 2.5 do livro do O'Rourke e o artigo de Keil e Snoeyink.
- 18 de maio (Aula 16):
Slides: [pdf]
Leitura recomendada: cap 5 do livro de de Berg e outros.
- 23 de maio (Aula 17):
- Fecho convexo
- Embrulho de presente
- Graham
- Incremental
- Lista 9
Slides: [pdf]
Leitura recomendada: sec 7.4 do FP, exceto pela sec 7.4.6.
- 25 de maio (Aula 18):
- Quickhull
- Cota inferior para fecho convexo
- Par de pontos mais distantes
Slides: [pdf]
Leitura recomendada: sec 7.4.6 do FP.
- 30 de maio (Aula 19):
Slides: [pdf]
Leitura recomendada: secs 3.6 e 3.8 do livro do O'Rourke e sec 3.2 do livro de Preparata e Shamos.
Junho