MAC0331  Geometria Computacional

Por | Em

OBJETIVOS:  Estudo de algoritmos, estruturas de dados e propriedades geométricas para a resolução de problemas de natureza geométrica.

Study of algorithms, data structures, and geometric properties used in the resolution of problems of a geometric nature.

PROGRAMA RESUMIDO:  Triangulação e particionamento de polígonos, fechos convexos 2D e 3D, diagramas de Voronoi, problemas de localização, interseção e proximidade, arranjos de retas no plano, ladrilhamentos do Rn.

Polygon triangulation and partitioning, 2D and 3D convex hulls, Voronoi diagrams, search, intersection and proximity problems, arrangements, tilings in Rn.

PROGRAMA:  Triangulação de polígonos: teoria, primitivas geométricas, problemas de galeria de arte, 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. Ladrilhamentos no Rd.

Polygon triangulation: theory, geometric primitives, art gallery problems, algorithms, implementation issues. Polygon partitioning: partitions of monotone polygons, trapezoidal decompositions, partitions in convex polygons. Convex hull in two dimensions: gift wrapping, quickhull, Graham, incremental, divide and conquer algorithms; complexity lower bound. Convex hull in three dimensions: polyhedral, regular polytopes, Euler formula, data structures, geometric primitives, gift wrapping algorithm. Voronoi diagrams: properties, Delaunay diagram, lower bound, geometric primitives, quadratic algorithm, divide and conquer algorithm. Search and intersection: location of point in polygon. Proximity problems: closest pair of points, minimum spanning trees. Arrangements. Tilings in R^d.

RESPONSÁVEL:  Cristina Gomes Fernandes,

PRÉ-REQUISITOS:  MAC0323.

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étodo: provas, exercícios, e exercícios-programa.
Critério: média ponderada de provas e exercícios.
Norma de recuperação: média ponderada entre a nota final, a nota na prova de recuperação e um eventual exercício-programa.

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.
  • C.G. Fernandes, J.C. de Pina, Convite à Geometria Computacional, Em: André C.P.L.F. de Carvalho; Tomasz Kowaltowski. (Org.). JAI - XXVIII Jornadas de Atualização em Informática. Rio de Janeiro: PUC-Rio, 2009, v. XXVIII, p. 331-380. Capítulo 7.
  • 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.
  • S.L. Devadoss, J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011.

OBSERVAÇÃO:  Disciplina optativa eletiva no currículo do BCC.

 

[Veja dados da disciplina no JúpiterWeb]

Oferecimentos recentes da disciplina: 2006/1, 2004/2, 2002/2, 2001/1, 2000/1, 1999/2, 1997/2