CAPG003 - Geometria Computacional

Carga horária: 45 horas-aula (3 créditos)

Ementa: Projeto e análise de algoritmos para problemas em geometria computacional. Triangularização de polígonos. Particionamento de polígonos. Envoltória convexa. Diagrama de Voronoi e Triangulação de Delaunay. Problemas de localização e intersecção. Problemas de proximidade. Arranjos de retas no plano. Questões de análise de complexidade e modelos computacionais. Aplicações à computação gráfica, planejamento de movimento, casamento de padrões.

Bibliografia:

• M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, 2nd ed., Springer-Verlag, 2000.

• P.J. de Resende, J. Stolfi, Fundamentos de Geometria Computacional, IX Escola de Computação, 1994.

• L.H. Figueiredo, P.C.P. Carvalho, Introdução à Geometria Computacional, 18o. Colóquio Brasileiro de Matemática, IMPA, 1991.

• M.J. Laszlo, Computational Geometry and Computer Graphics in C++, Prentice Hall, 1996.

• J. O'Rourke, Computational Geometry in C, Cambridge University Press, 1993.

• F.P. Preparata, M.I. Shamos, Computational Geometry: an Introduction, Texts and Monographs in Computer Science, Springer-Verlag, 1985.