Programação das aulas

Agosto

• 18 de agosto (Aula 1):
  • Informações gerais e introdução [pdf | ps.gz]
  • Par de pontos mais próximos
  Transparências [pdf | ps.gz]

• 20 de agosto (Aula 2):
  • Par de pontos mais próximos no plano
  • Primeira tarefa para dia 12 de setembro
  Transparências [pdf | ps.gz]
  Leitura recomendada: sec. 33.4 do CLRS ou sec. 7.3 do FP.
  Você encontra esse algoritmo descrito também no cap 8 de Laszlo, e no capítulo 5 de Preparata e Shamos.
  

• 25 de agosto (Aula 3):
  • Teorema da Galeria de Arte
  • Definições e preliminares
  • Lista 1
  Transparências [pdf | ps.gz].
  Leitura recomendada: seção 1 das notas de aula [pdf | ps.gz] e/ou seção 1.1 do O'Rourke.

• 27 de agosto (Aula 4):
  • Teorema da Galeria de Arte
  • Orelhas, triangularizações e colorações
  • Alguns predicados geométricos
  • Lista 2
  Leitura recomendada: notas de aula (versão revisada) [pdf | ps.gz] e/ou sec 1.2 e 1.3 do O'Rourke.
  Transparências: [pdf| ps.gz]

• 1 de setembro (Aula 5):
  • Primitivas
  • Algoritmos de triangularização
  Leitura recomendada: restante do cap 1 do O'Rourke.
  Transparências: [pdf | ps.gz]
  

• 3 de setembro:
  • Palestra do Howard Karloff

• 15 de setembro (Aula 6):
  • Detecção de interseção de segmentos
  • Método da linha de varredura
  Leitura recomendada: sec 33.2 do CLRS e sec 7.5 do FP.
  Transparências: [pdf | ps.gz]

• 17 de setembro (Aula 7):
  • Algoritmo de Shamos e Hoey para detecção de interseção de segmentos
  • Lista 3
  Leitura recomendada: sec 33.2 do CLRS e sec 7.5 do FP.
  Transparências: [pdf | ps.gz]

• 22 de setembro (Aula 8):
  • Algoritmo de Bentley e Ottmann
  Leitura recomendada: sec 2.1 do livro de de Berg e outros.
  Transparências: [pdf | ps.gz]

• 24 de setembro (Aula 9):
  • Triangulação de polígonos monótonos
  Leitura recomendada: sec 3.3 do livro de Berg e outros.
  Transparências: [pdf | ps.gz]

• 29 de setembro (Aula 10):
  • Trapezoidalização, pontas interiores, etc
  • Primeiro caso do algoritmo de Lee e Preparata
  Leitura recomendada: começo da sec 7.6 do FP.
  Transparências: [pdf | ps.gz]

• 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.]