MAC-331 GEOMETRIA COMPUTACIONAL
- OBJETIVOS: Estudo de algoritmos, estruturas de dados e
propriedades geométricas para a solução de problemas de natureza
geométrica.
- CONTEÚDO:
Triangularização de polígonos:
teoria, algoritmos e questões de implementação.
Partição de polígonos:
partição em polígonos monótonos,
trapezoidalização de um polígono,
partição de um polígono em partes convexas.
Fecho convexo no plano:
o método do embrulho para presente,
algoritmo Quickhull,
algoritmo de Graham,
algoritmo incremental,
algoritmo de divisão-e-consquista,
cota inferior.
Fecho convexo tridimensional:
poliedro,
politopos regulares,
fórmula de Euler,
estruturas de dados,
algoritmo do embrulho para presente.
Diagrama de Voronoi:
propriedades do diagrama de Voronoi
diagrama de Delaunay
cota inferior
uma primitiva geométrica: InCircle
um algoritmo quadrático
um algoritmo de divisão-e-conquista
aplicações.
Problema 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.
Arranjos de retas no plano.
- PRÉ-REQUISITOS: MAC-122.
- CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos.
- 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, and
O. Schwarzkopf,
Computational Geometry, Algorithms and Applications,
Springer Verlag, 1997 (second edition, 2000).
- T.H. Cormen,
C.E. Leiserson, and
R.L. Rivest,
Introduction to algorithms,
The MIT Press, McGraw-Hill Book Company, 1990, QA758 C811i.
-
H. Edelsbrunner,
Algorithms in Combinatorial Geometry,
EATCS Monographs on Theoretical Computer Science, no. 10,
Springer-Verlag, Berlin, 1987, QA758 E21a.
- L.H. Figueiredo and
P.C.P. Carvalho,
Introdução à geometria computacional,
18o. Colóquio Brasileiro de Matemática,
IMPA, 1991,
QA758 F475i.
- M.J. Laszlo,
Computational Geometry and Computer Graphics in C++,
Prentice Hall, Upper Saddle River, NJ, 1996.
-
J. O'Rourke,
Computational Geometry in C,
Cambridge University Press, Cambridge, 1994 [second edition, 1998].
-
F.P. Preparata and
M.I. Shamos,
Computational Geometry: An Introduction,
Texts and Monographs in Computer Science,
Springer-Verlag, New York, 1985, QA758 P927c.
- P.J. de Resende, and
J. Stolfi,
Fundamentos de geometria computacional,
IX Escola de Computação, 1994.
MAC 5747's
Home Page.
Last modified: Wed Feb 2 15:08:09 EDT 2000