Português English
Contato

Lista de Disciplinas | CMP189

Algoritmos Geométricos

Responsável: João Luiz Dihl Comba
Pré-Requisitos: –
Carga Horária: 60 hs
Créditos: 4
Semestres Oferecidos: Segundo semestre
Matrícula de Graduandos: A matricula deverá ser feita como Aluno Especial
Página da Disciplina: –

SÚMULA

Fundamentos. Interseções de Segmentos de Linha. Particionamento de Polígonos. Envoltórias Convexas. Diagramas de Voronoi e Triangulações de Delaunay. Algoritmos de Busca Pontual e Intervalar. kd-trees, R-trees, Quadtrees, BSP-trees. Grafos de Visibilidade, Planejamento de Movimento

OBJETIVOS

A disciplina tem como objetivo estudar estruturas de dados e algoritmos geométricos, os quais possuem aplicações em diversos campos, como a computação gráfica, sistemas geográficos de informação, bancos de dados, processamento de imagens, projeto de circuito integrados, robótica, visão por computador, entre outros

PROGRAMA

• Fundamentos: Discutir e motivar a necessidade de se estudar algoritmos geométricos. Revisar conceitos básicos de análise de algoritmos. (2 sessões)
• Interseções de Segmentos de Linha . (2 sessões)
• Particionamento de Polígonos: Particionamento monotônico. Particionamento Trapezoidal. Triangulações. Problema da Galeria de Arte. (2 sessões)
• Envoltórias Convexas: Algoritmos 2D: GiftWrap, Graham, QuickHull, Incremental. Algoritmos 3D. (2 sessões)
• Diagramas de Voronoi e Triangulações de Delaunay: Definição e Propriedades do Diagrama de Voronoi. Algoritmo de Fortune. Propriedades de triangulações de Delaunay. Aplicações. . (4 sessões)
• Arranjos e Dualidade: (2 sessões)
• Algoritmos de Busca Intervalar: Kd-trees. R-trees. Algoritmo de cascadeamento fracional. (2 sessões)
• Algoritmos de Busca Pontual: Definição. Algoritmos de busca pontual usando mapas trapezoidais. (2 sessões)
• Quadtrees: Representação. Algoritmos de Construção. Cálculo de Propriedades Geométricas. Operações Booleanas e Transformações Lineares. Octrees. (2 sessões)
• BSP-trees. Definição. Cálculo de Visibilidade. Algoritmos de construção. Operações Booleanas entre BSP-trees. Aplicações a jogos. (2 sessões)
• Outras Estruturas de Dados Geométricas: Interval trees, Segment Trees. (2 sessão)
• Grafos de Visibilidade: Definição e algoritmos de construção. Planejamento de movimento de robôs. (2 sessões)
• Planejamento de Movimento: Somas de Minkowski, Planejamentos translacionais e rotacionais. (2 sessões)

CRITÉRIOS DE AVALIAÇÃO

A avaliação considera o resultado de trabalhos teóricos, provas e um trabalho final de implementação.

BIBLIOGRAFIA

• Computational Geometry: Algorithms and Applications. M. de Berg, M. van Kreveld, M. Overmars, O. Scwarzkopf. Springer Verlag, 1997.
• Computational Geometry in C. Joseph O’Rourke. Cambridge University Press, 1993.
• Applications of Spatial Data Structures. Hanan Samet. Academic Press, 1990.
• Introduction to Algorithms. Cormen, Leiserson, Rivest. McGraw Hill.