CCT-UFCA/Ciência da Computação/Geometria Computacional
Programa do Componente Curricular
[editar | editar código]| Código: | |||||||||
| Componente Curricular: | Geometria Computacional | ||||||||
| Semestre de Oferta: | Tipo: | Disciplina | Caráter: | Optativa | |||||
| Unidade Acadêmica Responsável: | Centro de Ciências e Tecnologia - CCT | ||||||||
| Área: | Teoria da Computação | ||||||||
| Créditos: | 4 | Carga horária: | 64 | Teórica: | 64 | Prática: | 0 | Extensão: | - |
| Pré-requisito: | CC0062 - Laboratório de Algoritmos e Estruturas de Dados e CC0065 - Construção e Análise de Algoritmos | ||||||||
| Co-requisito: | |||||||||
| Equivalência: | |||||||||
Objetivos
[editar | editar código]Estudo de algoritmos, estruturas de dados e propriedades geométricas para a solução de problemas de natureza geométrica.
Ementa
[editar | editar código]Triangularização de polígonos: teoria, primitivas geométricas, 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 embrulhopara-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.
Conteúdo
[editar | editar código]Metodologia
[editar | editar código]Avaliação
[editar | editar código]Bibliografia Básica
[editar | editar código]- DE RESENDE, P. J.; STOLFI, J. Fundamentos de Geometria Computacional, IX Escola de Computação, 1994.
- FERNANDES, C. G.; DE PINA, J. C. Convite à Geometria Computacional, (Org.). JAI - XXVIII Jornadas de Atualização em Informática. Rio de Janeiro: PUC-Rio, 2009, v. XXVIII, p. 331- 380. Capítulo 7
- FIGUEIREDO, L. H.; CARVALHO, P. C. P. Introdução à Geometria Computacional, 18o. Colóquio Brasileiro de Matemática, IMPA, 1991. ISBN 85-244-0061-7
Bibliografia Complementar
[editar | editar código]- DE BERG, M.; OVERMARS, M.; VAN KREVELD, M.; CHEONG, O. A Computacional geometry: algoritms and applications. 3 ed. Springer, 2008. ISBN-10: 3540779736; ISBN-13: 978-3540779735
- MULMULEY, K. Computacional geometry: an introduction through randomized algorithms, Prentice Hall, 1994. ISBN-10: 0133363635; ISBN-13: 978-0133363630
- PREPARATA, F. P.; SHANVOS, M. I. Computacional geometry: an introduction. 1st ed. 1985. Corr. 5th printing 1993. Springer, 1985. ISBN-10: 0387961313; ISBN-13: 978- 0387961316
- GHALI, S. Introduction to Geometric Computing. Springer, 2008. ISBN-10: 1848001142; ISBN-13: 978-1848001145
- ROURKE, J. O. Computational Geometry in C. 2 ed. Cambridge University Press, 1998. ISBN-10: 0521649765; ISBN-13: 978-0521649766