MAC 5747 - Geometria Computacional

Docente Responsável: Carlos Eduardo Ferreira
José Augusto Ramos Soares

Objetivos: O objetivo desse curso é apresentar técnicas, algoritmos e estruturas de dados usados para a resolução de problemas geométricos por computador. Pretendemos mostrar estratégias clássicas de solução de problemas geométricos, assim como apresentar possivelmente temas de pesquisa.

Justificativa: Geometria Computacional é uma área de pesquisa de grande interesse em Ciência da Computação, encontrando aplicações em diversas outras áreas como, por exemplo, computação gráfica e processamento de imagens.

Conteúdo:

• Estruturas básicas para representação de entidades geométricas: pontos, retas, segmentos, polígonos e planos. Manipulação de estruturas geométricas: fórmulas geométricas, transformações projetivas.

• Apresentação de problemas geométricos clássicos: busca, problemas de proximidade, localização de pontos, intersecção, determinação de fecho convexo.

• Estruturas geométricas e suas aplicações: diagrama de Voronoi, triangulação de Delaunay, grafo de Gabriel.

• Implementação de algoritmos geométricos.

1.

H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer, Berlin, 1987.

2.

L.H. de Figueiredo and P.C.P. Carvalho, Introdução à Geometria Computacional, XVIII Coloq. Bras. de Matem., IMPA, Rio de Janeiro, 1991.

3.

F.P. Preparata and M.I. Shamos, Computational Geometry: an Introduction, Springer, New York, 1985.

4.

P.J. de Rezende and J. Stolfi, Fundamentos de Geometria Computacional, IX Escola de Computação, Recife, 1994.