Programação das aulas

Agosto

• 6 de agosto (Aula 1):
  • Introdução [pdf | ps.gz]
  • Problema do par de pontos mais próximos

• 8 de agosto (Aula 2):
  • Par de pontos mais próximos no plano [anotações e exercícios]
    Transparências [pdf | ps.gz]
  • Teorema da Galeria de Arte
  • Primeira tarefa para dia 18 de agosto
  Leitura recomendada: sec. 33.4 do CLRS. Você encontra esse algoritmo descrito também no cap 8 de Laszlo (veja as referências bibliográficas), e no capítulo 5 de Preparata e Shamos.
  Se você ficou curioso para ver a prova de cota inferior para o problema da unicidade de elementos (n-element distinctness problem), olhe o capítulo 1 do Preparata e Shamos.

• 13 de agosto (Aula 3):
  • Teorema da Galeria de Arte
  • Definições e preliminares [pdf | ps.gz ]
  Leitura recomendada: cap 1 do O'Rourke.
  Transparências [pdf].

• 15 de agosto (Aula 4):
  • Teorema da Galeria de Arte
  • Orelhas, triangularizações e colorações
  • Áreas
  Transparências: [pdf]

• 20 de agosto (Aula 5):
  • Primitivas
  • Algoritmos de triangularização
  Transparências: [pdf]
  Primitivas escritas em java, pelo Rafael Cosentino [tgz]

• 22 de agosto (Aula 6):
  • Intersecção de segmentos
  Leitura recomendada: Sec 33.2 do CLRS.

• 27 de agosto (Aula 7):
  • Intersecção de segmentos
  • Triangularização de polígonos monótonos
  Transparências: [pdf] [ps.gz]
  Leitura recomendada: cap 2 do O'Rourke e cap 3 do livro de Berg e outros.

• 29 de agosto (Aula 8):
  • Triangularização de polígonos monótonos
  • Tarefa 3
  • Trapezoidalização horizontal
  • Partição de polígonos em polígonos monótonos
  Transparências: [pdf] [ps.gz]
  Leitura recomendada: cap 2 do O'Rourke (muito compacto) e cap 3 do livro de Berg e outros (mais detalhado).