Programação das aulas

Agosto

Setembro

• 3 e 5 de setembro: Semana da Pátria (não há aula)

• 10 de setembro:
  • Primeira prova
  Matéria da prova: problema da galeria de arte, par mais próximo, primitivas, intersecção de segmentos, triangularização de polígonos, de polígonos monótonos.

• 12 de setembro (Aula 9):
  • Triangularização: Algoritmo de Lee e Preparata
  • Tarefa 4
  • Lista 4
  Transparências: [pdf] [ps.gz]

• 17 de setembro (Aula 10):
  • Partiçao convexa: Algoritmo de Hertel e Mehlhorn
  Leitura recomendada: o capítulo do O'Rourke que fala de triangularização de polígono, e do algoritmo de Lee e Preparata, fala de partição convexa e do algoritmo de Hertel e Mehlhorn.

• 19 de setembro (Aula 11):
  • Localização de pontos
  • Winding number e ray crossings (algoritmos lineares)
  • Pré-processamento quadrático com linha de varredura, para consultas logarítmicas
  • Tarefa 5
  • Lista 5
  Transparências: [pdf] [ps.gz]
  Leitura recomendada: uma das seções do capítulo 7 do O'Rourke (algoritmos das transparências), e seção 2.2.1 e uma parte da seção 2.2.2 (algoritmo da linha de varredura) do livro de Lee e Preparata. A segunda parte da seção 2.2.2 descreve o método mais rápido (que mencionei apenas brevemente, que tem a ver com partição em polígonos monótonos).

• 24 de setembro (Aula 12):
  • Casco convexo: definições e primeiros algoritmos
  Leitura recomendada: parte inicial do capítulo 3 do O'Rourke.

• 26 de setembro (Aula 13):
  • Casco convexo: quickhull e Graham
  Leitura recomendada: seções 3.4 e 3.5 do O'Rourke; 3.3.2 e 3.3.4 do Preparata e Shamos.