CMP189 - Algoritmos Geométricos – 2008/1 - Prof. João Comba                             

 

  • Aulas: Seg-Qua (10:30-12:10), Sala 102, Prédio 43424
  • Contato: Sala 230, Prédio 43425, ramal 6930
  • E-mail: comba “@” inf.ufrgs.br

cover 2cover2

 

Calendário, Conteúdo e Material Didático das Aulas                  

Aula

Data

Conteúdo

Leituras

01

10/03

Motivação. Exemplo: Envoltória Convexa. (slides  aula 1-3)

Cap 1 de Berg

02

12/03

Complexidade de Algoritmos. Algoritmo para Envoltória Convexa 2D.

Cap 3 O’Rourke, Cap 3 Cormen

03

17/03

Complexidade de Algoritmos. Algoritmo para Envoltória Convexa 2D.

Cap 3 O’Rourke, Cap 3 Cormen

04

19/03

Interseção de Segmentos de Linhas .  (slides  aula 4-7)

Cap 2 de Berg

05

24/03

Interseção de Segmentos de Linhas

Cap 2 de Berg

Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams
26/03 Recesso: Deadline IEEE Visualization 2008

06

3103

Interseção de Segmentos de Linhas.

Cap 2 de Berg

Comparação de Estruturas de Dados para Subdivisões Planares Baseada em Transições 

07

02/04

Particionamento de Polígonos  (slides  aula 8-10)

Cap 3 de Berg

08

07/04

Particionamento de Polígonos

Cap 3 de Berg

09

09/04

Particionamento de Polígonos

Cap 3 de Berg

10

14/04

Programação Linear (slides  aula 11-12)

Cap 4 de Berg

11

16/04

Programação Linear

Cap 4 de Berg
21/04 Feriado: Tiradentes

12

23/04

Programação Linear

Cap 4 de Berg
28/04 Recesso: Banca de Doutorado, Universiade de Utah, Estados Unidos
30/04 Recesso: Banca de Doutorado, Universiade de Utah, Estados Unidos

13

05/05

Algoritmos de Busca Intervalar (slides  aula 13-14)

Cap 5 de Berg

14

07/05

Algoritmos de Busca Intervalar

Cap 5 de Berg

15

12/05

Algoritmos de Busca Pontual  (slides  aula 15-16)

Cap 6 de Berg

16

14/05

Algoritmos de Busca Pontual

Cap 6 de Berg

17

19/05

Algoritmos de Busca Pontual

Cap 8 de Berg
18 21/05

Propostas de Trabalhos, Abstrat e Related Work
26/05 Recesso Semana Acadêmica
28/05 Recesso Semana Acadêmica

19

02/06

Diagramas de Voronoi(slides  aula 19-20)

Cap 8 de Berg

20

04/06

Diagramas de Voronoi 

Cap 7 de Berg
21 09/06

Arranjos e Dualidade (slides  aula 21)

 Cap 9 de Berg

22

11/06

Triangulações de Delaunay (slides  aula 22-23)

Cap 9 de Berg

23

16/06

Triangulações de Delaunay 

Cap 10 de Berg

24

18/06

Estruturas de Dados Geométricas: Segment Trees, Interval Trees. (slides  aula 24)

Cap 10 de Berg

25

23/06

BSP-Trees (slides  aula 25)

Cap 14 de Berg

26

25/06

Quadtrees (slides  aula 26)

Cap 12 de Berg

27

30/06

Planejamento de Movimento de Robôs (slides  aula 27)

Cap 13 de Berg

28

02/07

Prova Final

29

07/07

Apresentação dos Trabalhos Finais

 

30

09/07

Apresentação dos Trabalhos Finais

 

 

Avaliação


A avaliação constará de notas de trabalhos práticos, trabalho final, artigo sobre o trabalho final e prova. A nota final será calculada da seguinte forma:

 

(MT * 4.0 + TF * 2.0 + ARTIGO * 2.0 + PROVA * 2.0), onde:

 

Bibiografia

 
BIBLIOGRAFIA BÁSICA:

BIBLIOGRAFIA COMPLEMENTAR:

Links