Disciplina
Informações da Disciplina

 Preparar para impressão 
Júpiter - Sistema de Graduação

Instituto de Matemática e Estatística
 
Ciência da Computação
 
Disciplina: MAC0331 - Geometria Computacional

Créditos Aula: 4
Créditos Trabalho: 0
Tipo: Semestral

Objetivos
Estudo de algoritmos, estruturas de dados e propriedades geométricas para a solução de problemas de natureza geométrica.
 
Docente(s) Responsável(eis)
Cristina Gomes Fernandes
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.
 
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.
 
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.
 
Requisitos
Os Requisitos variam conforme o curso para o qual ela é oferecida.

Clique para consultar o oferecimento para MAC0331.

Créditos | Fale conosco
© 1999 - 2024 - Superintendência de Tecnologia da Informação/USP