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:
  1. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry, Algorithms and Applications, Springer Verlag, 1997 (second edition, 2000).
  2. T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to algorithms, The MIT Press, McGraw-Hill Book Company, 1990, QA758 C811i.
  3. H. Edelsbrunner, Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, no. 10, Springer-Verlag, Berlin, 1987, QA758 E21a.
  4. L.H. Figueiredo and P.C.P. Carvalho, Introdução à geometria computacional, 18o. Colóquio Brasileiro de Matemática, IMPA, 1991, QA758 F475i.
  5. M.J. Laszlo, Computational Geometry and Computer Graphics in C++, Prentice Hall, Upper Saddle River, NJ, 1996.
  6. J. O'Rourke, Computational Geometry in C, Cambridge University Press, Cambridge, 1994 [second edition, 1998].
  7. F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985, QA758 P927c.
  8. P.J. de Resende, and J. Stolfi, Fundamentos de geometria computacional, IX Escola de Computação, 1994.