MAC0331 Geometria Computacional
OBJETIVOS: Estudo de algoritmos, estruturas de dados e propriedades geométricas para a solução de problemas de natureza geométrica.
PROGRAMA: Triangularização de polígonos: teoria, primitivas geométricas, algoritmos, questões de implementação. Particionamento de polígonos: particionamento em polígonos monótonos, trapezoidalização de polígonos, particionamento em polígonos convexos. Fecho convexo no plano: algoritmo embrulho-para-presente, algoritmo Quickhull, algoritmo de Graham, algoritmo incremental, algoritmo de divisão-e-conquista, cota inferior. Fecho convexo tridimensional: poliedros, politopos regulares, fórmula de Euler, estruturas de dados, primitivas geométricas, algoritmo embrulho-para-presente. Diagrama de Voronoi: propriedades, diagrama de Delaunay, cota inferior, primitivas geométricas, algoritmo quadrático, algoritmo de divisão-e-conquista. Problemas de localização e intersecção: localização de pontos em polígonos, intersecção de polígonos convexos, intersecção de semiplanos, núcleo de um polígono. Problemas de proximidade: problema do par-mais-próximo, árvore geradora mínima. Arranjos de retas no plano.
PRÉ-REQUISITOS: MAC0122.
PRÉ-REQUISITO NÃO-OFICIAL: MAC0338.
CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-aula.
CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.
BIBLIOGRAFIA BÁSICA:
- 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.
OBSERVAÇÃO: Disciplina optativa eletiva no currículo do BCC.
[Veja dados da disciplina no JúpiterWeb]