CC443: Algoritmos Geométricos

(2012/2013)
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto


Caracterização


Objectivos

Conhecer e saber implementar algoritmos e estruturas de dados eficientes para resolução de problemas geométricos no plano, com aplicações relevantes em Computação Gráfica, Robótica, Desenho Assistido por Computador, Sistemas de Informação Geográfica, Biologia Molecular e Análise de Dados.

Programa

Conceitos e ferramentas básicas em Geometria Computacional. Técnicas de varrimento do plano. Algoritmos para determinação do invólucro convexo de um conjunto de pontos. Algoritmos para decomposição de polígonos: partição de polígonos ortogonais em rectângulos alinhados, triangulação de polígonos monótonos e triangulação de polígonos genéricos. Noções de visibilidade no plano: introdução ao problema da Galeria de Arte e variantes. Algoritmos para identificar as intersecções dos segmentos de recta de um conjunto. Decomposições planares: algoritmo para determinar a sobreposição de duas decomposições e sua aplicação para obter a intersecção, união e diferença de duas decomposições planares (temáticas). Algoritmo para determinação do arranjo de um conjunto de rectas complanares (teorema da zona e complexidade do arranjo). Algoritmos para localização de pontos em regiões rectangulares. Problemas de proximidade. Diagrama de Voronoi e triangulação de Delaunay de um conjunto de pontos no plano: algoritmos para sua determinação e propriedades. Estruturas de dados para problemas geométricos. Aplicações.


Avaliação


Aulas


Bibliografia

Ligações interessantes ou úteis


Ana Paula Tomás, Departamento de Ciência de Computadores, FCUP, Universidade do Porto, 2012