CC443: Algoritmos Geométricos

(2007/08)
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto


Disciplina opcional do Mestrado em Ciência dos Computadores (2º Ciclo, S2) e do Mestrado integrado em Engenharia de Redes e Sistemas Informáticos da Faculdade de Ciências da Universidade do Porto.

Docente: Ana Paula Tomás

Objectivos

Conhecer e saber implementar algoritmos e estruturas de dados eficientes para resolução de problemas geométricos 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. Polígonos. Localização de pontos e proximidade. Convexidade. Invólucro convexo dum conjunto de pontos. Decomposição de polígonos (triangulação). Visibilidade no plano. Problema da Galeria de Arte e variantes. Intersecção de segmentos de recta e de polígonos. Arranjos. Diagramas de Voronoi e de Delaunay. Aplicações.

Créditos e Escolaridade

7.5 ECTS. 3 horas teóricas e 1.5 hora prática por semana.


Avaliação


Aulas


Bibliografia

Ligações úteis


Ana Paula Tomás, DCC-FC & LIACC, Universidade do Porto, 2008