Programação das aulas

Agosto e setembro

Outubro

• 1 de outubro:
  • Prova 1
  Matéria da prova: par de pontos mais próximos, teorema da galeria de arte, primitivas, cálculo de área de polígono, triangulação de polígonos (conceitos envolvidos e métodos vistos até agora), interseção de segmentos, método de linha de varredura. [Material coberto nas listas 1, 2 e 3.]

• 6 de outubro (Aula 11):
  • Algoritmo de Lee e Preparata (continuação)
  • Listas de arestas duplamente ligadas (doubly-connected edge lists)
  • Lista 4
  Transparências: [pdf] [ps.gz]
  Leitura recomendada: sec 7.6 do FP, cap 3 do livro de Berg e outros e, para o tópico de doubly-connected edge lists, a sec 2.2 do livro de Berg e outros.

• 8 de outubro (Aula 12):
  • Partições convexas
  • Algoritmo de Hertel e Mehlhorn
  Transparências: [pdf] [ps.gz]
  Leitura recomendada: sec 2.5 do O'Rourke.

• 20 de outubro (Aula 13):
  • Localização de pontos
  • Lista 5
  Transparências: [pdf] [ps.gz]
  Leitura recomendada: sec 7.4 do O'Rourke.

• 22 de outubro (Aula 14):
  • Diagrama de Voronoi
  Transparências: [pdf] [ps.gz]
  Leitura recomendada: sec 7.1 e começo da 7.2 do livro de de Berg e outros.

• 27 de outubro (Aula 15):
  • Algoritmo de Fortune
  Transparências: [pdf] [ps.gz]
  Leitura recomendada: metade da 7.2 do livro de de Berg e outros.

• 29 de outubro (Aula 16):
  • Algoritmo de Fortune
  • Relevos
  • Triangulações ângulo-ótimas e legais
  • Grafo de Delaunay
  • Lista 6
  Transparências: [pdf] [ps.gz]
  Leitura recomendada: sec. 7.2 e começo do cap 9 do livro de de Berg e outros.