Jupiterweb

Informações da Disciplina

Preparar para impressão

Júpiter - Sistema de Gestão Acadêmica da Pró-Reitoria de Graduação

Instituto de Matemática e Estatística

Ciência da Computação

Disciplina: MAC0331 - Geometria Computacional

Computacional Geometry

Créditos Aula:	4
Créditos Trabalho:	0
Carga Horária Total:	60 h
Tipo:	Semestral
Ativação:	01/01/2021	Desativação:

Objetivos

Estudo de algoritmos, estruturas de dados e propriedades geométricas para a soluçã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.

Docente(s) Responsável(eis)

	55029 - Cristina Gomes Fernandes
	91267 - Jose Coelho de Pina Junior

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.

Avaliação

Método

Média ponderada de provas, exercícios e projetos de programação.

Critério

A média geral deve ser maior ou igual a 5 para aprovação.

Norma de Recuperação

Em caso de média geral maior ou igual a 3 e menor que 5, a nova média geral consiste de uma média ponderada entre a média geral e uma prova e/ou projeto de recuperação.

Bibliografia

Bibliografia Básica: 

M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, 2nd ed., Springer-Verlag, 2000. 

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. 

J. O'Rourke, Computational Geometry in C, Cambridge University Press, 1993.

Bibliografia Complementar: 

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. 

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.

Clique para consultar os requisitos para MAC0331

Clique para consultar o oferecimento para MAC0331