Disciplina Discipline MAC5747
Geometria Computacional
Computational Geometry

Área de Concentração: 45134

Concentration area: 45134

Criação: 17/12/2021

Creation: 17/12/2021

Ativação: 17/12/2021

Activation: 17/12/2021

Nr. de Créditos: 8

Credits: 8

Carga Horária:

Workload:

Docentes Responsáveis:

Professors:

Cristina Gomes Fernandes

Jose Coelho de Pina Junior

Sinai Robins

Objetivos:

Estudo de algoritmos, estruturas de dados e propriedades geométricas para a solução de problemas de natureza geométrica

Objectives:

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

Justificativa:

Geometria Computacional é uma área de pesquisa de grande interesse em Ciência da Computação, encontrando aplicações em diversas outras áreas como, por exemplo, computação gráfica e processamento de imagens.

Rationale:

Computational Geometry is an area of research of great interest in Computer Science, with applications in several other areas such as computer graphics and image processing.

Conteúdo:

1. Triangularização de polígonos: teoria, primitivas geométricas, problemas de galeria de arte, algoritmos, questões de implementação. 2. Particionamento de polígonos: particionamento em polígonos monótonos, trapezoidalização de polígonos, particionamento em polígonos convexos. 3. Fecho convexo no plano: algoritmo embrulho-para-presente, algoritmo Quickhull, algoritmo de Graham, algoritmo incremental, algoritmo de divisão-e-conquista, cota inferior. 4. Fecho convexo tridimensional: poliedros, politopos regulares, fórmula de Euler, estruturas de dados, primitivas geométricas, algoritmo embrulho-para-presente. 5. Diagrama de Voronoi: propriedades, diagrama de Delaunay, cota inferior, primitivas geométricas, algoritmo quadrático, algoritmo de divisão-e-conquista. 6. 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. 7. Problemas de proximidade: problema do par-mais-próximo, árvore geradora mínima. 8. Arranjos de retas no plano. 9. Ladrilhamentos no R^d

Content:

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

Forma de Avaliação:

Média ponderada de provas, exercícios e, possivelmente, exercícios-programa.

Type of Assessment:

Weighted average on exams, homework, and possibly programming assignments.

Bibliografia:

1. S.L. Devadoss and J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011. 2. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, 2nd ed., Springer-Verlag, 2000. 3. P.J. de Rezende, J. Stolfi, Fundamentos de Geometria Computacional, IX Escola de Computação, 1994. 4. H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer, Berlin, 1987. 5. 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. 6. L.H. Figueiredo, P.C.P. Carvalho, Introdução à Geometria Computacional, 18o. Colóquio Brasileiro de Matemática, IMPA, 1991. 7. M.J. Laszlo, Computational Geometry and Computer Graphics in C++, Prentice Hall, 1996. 8. J. O'Rourke, Computational Geometry in C, 2nd ed., Cambridge University Press, 1998. 9. F.P. Preparata, M.I. Shamos, Computational Geometry: an Introduction, Texts and Monographs in Computer Science, Springer-Verlag, 1985.

Bibliography:

1. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, 2nd ed., Springer-Verlag, 2000. 2. P.J. de Rezende, J. Stolfi, Fundamentos de Geometria Computacional, IX Escola de Computação, 1994. 3. 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. 4. L.H. Figueiredo, P.C.P. Carvalho, Introdução à Geometria Computacional, 18o. Colóquio Brasileiro de Matemática, IMPA, 1991. 5. M.J. Laszlo, Computational Geometry and Computer Graphics in C++, Prentice Hall, 1996. 6. J. O'Rourke, Computational Geometry in C, 2nd ed., Cambridge University Press, 1998. 7. F.P. Preparata, M.I. Shamos, Computational Geometry: an Introduction, Texts and Monographs in Computer Science, Springer-Verlag, 1985. 8. S.L. Devadoss and J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011.

Tipo de oferecimento da disciplina:

Presencial

Class type:

Presencial