Programação das aulas
Segundo semestre de 2018
Agosto
- 6 de agosto (Aula 1):
- Informações gerais e introdução [pdf]
- Par de pontos mais próximos
Slides: [pdf]
Leitura recomendada: seções 7.1 a 7.3 do
FP ou seção 33.4 do CLRS.
Você encontra esse algoritmo descrito também no cap 8 de Laszlo,
e no capítulo 5 de Preparata e Shamos.
- 8 de agosto (Aula 2):
- Teorema da Galeria de Arte
- Definições e preliminares
- Orelhas, triangulações e colorações
- Lista 1
Slides: [pdf]
Leitura recomendada: seções 1 a 4 das
notas de aula [pdf] e/ou
seção 1.1 do O'Rourke. Veja também o verbete Art
gallery problem da Wiki.
- 13 de agosto (Aula 3):
- Teorema da Galeria de Arte
- Orelhas, triangulações e colorações
- Primitivas
- Algoritmos de triangularização
Slides: [pdf].
Leitura recomendada: restante das notas da aula passada e/ou sec 1.2 e 1.3 do O'Rourke.
- 15 de agosto (Aula 4):
- Teste de diagonal
- Algoritmos de triangularização usando orelhas
- Detecção de interseção de segmentos
- Método da linha de varredura
- Lista 2
Slides: [pdf]
Leitura recomendada: começo das sec 33.2 do CLRS e
sec 7.5 do FP.
- 20 de agosto (Aula 5):
- Método da linha de varredura
- Algoritmo de Shamos e Hoey para detecção de interseção de segmentos
- Tratamento dos casos degenerados
Slides: [pdf]
Leitura recomendada: sec 33.2 do CLRS e
sec 7.5 do FP.
- 22 de agosto (Aula 6):
- Detecção de todas as interseções de segmentos
- Algoritmo de Bentley e Ottmann
Slides: [pdf]
Leitura recomendada: sec 33.2 do CLRS e
sec 7.5 do FP.
- 27 de agosto (Aula 7):
- Triangulação de polígonos monótonos
- Lista 3
Slides: [pdf]
Leitura recomendada: sec 3.3 do livro de Berg e outros.
- 29 de agosto (Aula 8):
- Trapezoidalização, pontas interiores, etc
- Algoritmo de Lee e Preparata
Slides: [pdf]
Leitura recomendada: sec 7.6 do FP.
Setembro e demais meses