Informa??es da Disciplina

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

Instituto de Ciências Matemáticas e de Computação
 
Ciências de Computação
 
Disciplina: SCC0254 - Introdução à Geometria Computacional: Algoritmos e Aplicações
Introduction to Computational Geometry: algorithms and applications

Créditos Aula: 4
Créditos Trabalho: 2
Carga Horária Total: 120 h
Tipo: Semestral
Ativação: 01/01/2020 Desativação:

Objetivos
Apresentar conceitos e métodos básicos de Geometria Computacional, com foco nos algoritmos, estruturas de dados e em aplicações dos métodos em computação gráfica, robótica e programação competitiva. A disciplina deverá abordar como a Geometria Computacional permite modelar problemas de computação gráfica e ainda apresentar aspectos práticos da implementação de algoritmos comumente estudados em competições de programação.
 
Introduce students to concepts of computational geometry, with focus on algorithms, data structures and in applications of methods such as in computer graphics, robotics and competitive programming. The course approaches how the Computational Geometry allows to model computer graphic problems, as well as presenting practical aspects of algorithm implementation often studied in programming contests.
 
 
Docente(s) Responsável(eis)
793065 - João do Espírito Santo Batista Neto
 
Programa Resumido
Preliminares. Triangulação e particionamento de polígonos, Fecho convexo 2D e 3D. Arranjos. Teoremas de Proximidade: Diagramas de Voronoi. Métodos geométricos para localização. Técnicas de amostragem aleatória. Construção de bibliotecas para manipulação de pontos, linhas, círculos, triângulos e quadriláteros.
 
Basic concepts. Polygon triangulation and partitioning, 2D and 3D convex hulls. Arrangements. Proximity theorems: Voronoi diagrams and Delaunay triangulation. Geometric search. Random Sampling. Design of programming libraries for points, circles, triangles and quadrilaterals.
 
 
Programa
Preliminares: conceitos geométricos, tais como dualidade, modelos computacionais e limitantes inferiores. Triangulação de polígonos: teoria, primitivas geométricas, problemas de galeria de arte, algoritmos, questões de implementação. Fechos Convexos: propriedades e algoritmos. Arranjos: combinatória e arranjos, teorema de zona, algoritmos "sweep", seqüências de Davenport-Schinzel. Teoremas de proximidade: triangulação de Voronoi e Delaunay. Métodos Geométricos para localização: localização de pontos em coleções de hipersuperfícies, cascata fracionária. Técnicas de amostragem aleatórias. Visibilidade e problemas de distâncias mínimas. Planejamento do movimento de robôs: somas de Minkowski, Decomposição de Células, Movimento com 2 e 3 graus de liberdade. Problemas de programação competitiva: construção de bibliotecas para manipulação de pontos, linhas, círculos, triângulos e quadriláteros.
 
Basic geometric concepts such as duality, computational models and lower bounds. Convex Hull: properties and algorithms. Arrangements: combinatory and arrangements, the zone theorem, sweep algorithms, Davenport-Schinzel sequences. Proximity problems: Voronoi diagrams and Delaunay triangulation. Geometric searching: point location in collections of hypersurfaces, fractional cascading. Random sampling. Minimal distances and visibility problems. Robot motion planning: sums of Minkowski, cell decomposition, movement with 2 and 3 degrees of freedom. Competitive programming problems: design of programming libraries for points, circles, triangles and quadrilaterals
 
 
Avaliação
     
Método
Aulas expositivas teóricas e trabalhos práticos relacionados às áreas de computação gráfica e/ou robótica. Resolução de problemas em programação competitiva com correção automática.
Critério
Avaliação por meio de provas escritas, trabalhos práticos relacionados às áreas de computação gráfica, robótica e programação competitiva. Número de provas: no mínimo uma (01) e no máximo três (03) provas.
Norma de Recuperação
Critério de aprovação: a nota final (MF) do aluno que realizou provas de recuperação dependerá da média do semestre (MS) e da média das provas de recuperação (MR), como segue: • MF = 5 se 5 <= MR <= (10 - MS) • MF = (MS + MR) / 2 se MR > (10 - MS) • MF = MS se MR< 5
 
Bibliografia
     
Livros Textos: DE BERG, M; CHEONG, O.; VAN KREVELD, M.; OVERMARS, M. Computational Geometry: Algorithms and Applications. 3.ed, Springer. 2008. HALIM, S; HALIM, Felix. Competitive Programming 3. The new lower bound of programming contests. ICPC, 2013. VINCE, J. Geometry for Computer Graphics: Formulae, Examples and Proofs. Springer, 2005. Bibliografia Complementar: SKIENA, S.S.; REVILLA, M.A. Programming Challenges: The Programming Contest Training Manual. Springer, 2003. MULMULEY, K. Computacional geometry: an introduction through randomized algorithms, Prentice Hall, 1994. PREPARATA, F.P.; SHANVOS, M.I. Computational geometry: an introduction, Springer, 2 ed, 1988.
 

Clique para consultar os requisitos para SCC0254

Clique para consultar o oferecimento para SCC0254

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