Programação das aulas

Agosto

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

• 12 de agosto (Aula 2):
  • Par de pontos mais próximos no plano
  • Primeira tarefa para dia 20 de agosto
  • Lista 1
  Transparências [pdf] [ps.gz]
  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.
  Se você ficou curioso para ver a prova de cota inferior para o problema da unicidade de elementos (n-element distinctness problem), olhe as páginas 30-35 do Preparata e Shamos.

• 17 de agosto (Aula 3):
  • Teorema da Galeria de Arte
  • Definições e preliminares
  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. Veja também o verbete Art gallery problem da Wiki.

• 19 de agosto (Aula 4):
  • Teorema da Galeria de Arte
  • Orelhas, triangulações e colorações
  • Alguns predicados geométricos
  Leitura recomendada: restante das notas da aula passada e/ou sec 1.2 e 1.3 do O'Rourke.
  Transparências: [pdf] [ps.gz]

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

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

• 31 de agosto (Aula 7):
  • Detecção de todas as interseções de segmentos
  • Algoritmo de Bentley e Ottmann
  Leitura recomendada: sec 33.2 do CLRS e sec 7.5 do FP.
  Transparências: [pdf | ps.gz]