Programação das aulas
Primeiro semestre de 2022
Março
Abril
- 4 de abril (Aula 5):
- Método da linha de varredura
- Tratamento dos casos degenerados do algoritmo da aula passada
- Detecção de todas as interseções de segmentos
- Algoritmo de Bentley e Ottmann
- Segundo projeto
Slides: [pdf]
Leitura recomendada: sec 33.2 do CLRS e
sec 7.5 do FP.
- 6 de abril (Aula 6):
- Triangulação de polígonos monótonos
- Lista 5
Slides: [pdf]
Leitura recomendada: sec 3.3 do livro de de Berg e outros.
- 11 a 15 de abril: Não haverá aula - SEMANA SANTA
- 18 de abril (Aula 7):
- Trapezoidalização, pontas interiores, etc
- Algoritmo de Lee e Preparata
- Lista 6
Slides: [pdf]
Leitura recomendada: sec 7.6 do FP.
- 20 de abril (Aula 8):
- Como acoplar o algoritmo de Lee e Preparata e o algoritmo para polígonos y-monótonos?
- DCEL - Dobbly-Connected Edge List
- Diagrama de Voronoi
- Terceiro projeto
Slides: [pdf]
Leitura recomendada: secs 2.2 e 7.1 do livro de de Berg e outros.
- 25 de abril (Aula 9):
- Diagrama de Voronoi
- Algoritmo de Fortune
Slides: [pdf]
Leitura recomendada: cal 7 do livro de de Berg e outros.
Veja aqui uma aplicação curiosa de diagrama de Voronoi em jogos. Veja também aqui uma animação do algoritmo de Fortune que permite que se mexa tantos nos pontos da coleção quanto na posição da linha de varredura. Aqui você encontra uma explicação muito boa do algoritmo por Jacques Heunis, e detalhes sobre a implementação também.
- 27 de abril (Aula 10):
- Algoritmo de Fortune: casos degenerados
- Relevos
- Triangulações legais
- Grafo de Delaunay e triangulações de Delaunay
- Lista 7
Slides: [pdf]
Leitura recomendada: cap 9 até a sec 9.2 do livro de de Berg e outros.
Maio e demais meses