{"id":703,"date":"2015-12-30T09:42:19","date_gmt":"2015-12-30T11:42:19","guid":{"rendered":"http:\/\/www.inf.ufrgs.br\/profcomp_wp\/?page_id=703"},"modified":"2016-05-12T16:03:27","modified_gmt":"2016-05-12T19:03:27","slug":"cmp189","status":"publish","type":"page","link":"https:\/\/www.inf.ufrgs.br\/profcomp\/lista-de-disciplinas\/cmp189\/","title":{"rendered":"CMP189"},"content":{"rendered":"

Algoritmos Geom\u00e9tricos<\/strong><\/h3>\n

Respons\u00e1vel<\/b>: Jo\u00e3o Luiz Dihl Comba<\/a>
\nPr\u00e9-Requisitos<\/b>: –
\nCarga Hor\u00e1ria<\/b>: 60 hs
\nCr\u00e9ditos<\/b>: 4
\nSemestres Oferecidos<\/b>: Segundo semestre
\nMatr\u00edcula de Graduandos<\/b>: A matricula dever\u00e1 ser feita como Aluno Especial
\nP\u00e1gina da Disciplina<\/b>: –<\/p>\n

S\u00daMULA<\/strong><\/p>\n

Fundamentos. Interse\u00e7\u00f5es de Segmentos de Linha. Particionamento de Pol\u00edgonos. Envolt\u00f3rias Convexas. Diagramas de Voronoi e Triangula\u00e7\u00f5es de Delaunay. Algoritmos de Busca Pontual e Intervalar. kd-trees, R-trees, Quadtrees, BSP-trees. Grafos de Visibilidade, Planejamento de Movimento<\/p>\n

OBJETIVOS<\/strong><\/p>\n

A disciplina tem como objetivo estudar estruturas de dados e algoritmos geom\u00e9tricos, os quais possuem aplica\u00e7\u00f5es em diversos campos, como a computa\u00e7\u00e3o gr\u00e1fica, sistemas geogr\u00e1ficos de informa\u00e7\u00e3o, bancos de dados, processamento de imagens, projeto de circuito integrados, rob\u00f3tica, vis\u00e3o por computador, entre outros<\/p>\n

PROGRAMA<\/strong><\/p>\n

\u2022 Fundamentos: Discutir e motivar a necessidade de se estudar algoritmos geom\u00e9tricos. Revisar conceitos b\u00e1sicos de an\u00e1lise de algoritmos. (2 sess\u00f5es)
\n\u2022 Interse\u00e7\u00f5es de Segmentos de Linha . (2 sess\u00f5es)
\n\u2022 Particionamento de Pol\u00edgonos: Particionamento monot\u00f4nico. Particionamento Trapezoidal. Triangula\u00e7\u00f5es. Problema da Galeria de Arte. (2 sess\u00f5es)
\n\u2022 Envolt\u00f3rias Convexas: Algoritmos 2D: GiftWrap, Graham, QuickHull, Incremental. Algoritmos 3D. (2 sess\u00f5es)
\n\u2022 Diagramas de Voronoi e Triangula\u00e7\u00f5es de Delaunay: Defini\u00e7\u00e3o e Propriedades do Diagrama de Voronoi. Algoritmo de Fortune. Propriedades de triangula\u00e7\u00f5es de Delaunay. Aplica\u00e7\u00f5es. . (4 sess\u00f5es)
\n\u2022 Arranjos e Dualidade: (2 sess\u00f5es)
\n\u2022 Algoritmos de Busca Intervalar: Kd-trees. R-trees. Algoritmo de cascadeamento fracional. (2 sess\u00f5es)
\n\u2022 Algoritmos de Busca Pontual: Defini\u00e7\u00e3o. Algoritmos de busca pontual usando mapas trapezoidais. (2 sess\u00f5es)
\n\u2022 Quadtrees: Representa\u00e7\u00e3o. Algoritmos de Constru\u00e7\u00e3o. C\u00e1lculo de Propriedades Geom\u00e9tricas. Opera\u00e7\u00f5es Booleanas e Transforma\u00e7\u00f5es Lineares. Octrees. (2 sess\u00f5es)
\n\u2022 BSP-trees. Defini\u00e7\u00e3o. C\u00e1lculo de Visibilidade. Algoritmos de constru\u00e7\u00e3o. Opera\u00e7\u00f5es Booleanas entre BSP-trees. Aplica\u00e7\u00f5es a jogos. (2 sess\u00f5es)
\n\u2022 Outras Estruturas de Dados Geom\u00e9tricas: Interval trees, Segment Trees. (2 sess\u00e3o)
\n\u2022 Grafos de Visibilidade: Defini\u00e7\u00e3o e algoritmos de constru\u00e7\u00e3o. Planejamento de movimento de rob\u00f4s. (2 sess\u00f5es)
\n\u2022 Planejamento de Movimento: Somas de Minkowski, Planejamentos translacionais e rotacionais. (2 sess\u00f5es)<\/p>\n

CRIT\u00c9RIOS DE AVALIA\u00c7\u00c3O<\/strong><\/p>\n

A avalia\u00e7\u00e3o considera o resultado de trabalhos te\u00f3ricos, provas e um trabalho final de implementa\u00e7\u00e3o.<\/p>\n

BIBLIOGRAFIA<\/strong><\/p>\n

\u2022 Computational Geometry: Algorithms and Applications. M. de Berg, M. van Kreveld, M. Overmars, O. Scwarzkopf. Springer Verlag, 1997.
\n\u2022 Computational Geometry in C. Joseph O\u2019Rourke. Cambridge University Press, 1993.
\n\u2022 Applications of Spatial Data Structures. Hanan Samet. Academic Press, 1990.
\n\u2022 Introduction to Algorithms. Cormen, Leiserson, Rivest. McGraw Hill.<\/p>\n","protected":false},"excerpt":{"rendered":"

Algoritmos Geom\u00e9tricos Respons\u00e1vel: Jo\u00e3o Luiz Dihl Comba Pr\u00e9-Requisitos: – Carga Hor\u00e1ria: 60 hs Cr\u00e9ditos: 4 Semestres Oferecidos: Segundo semestre Matr\u00edcula de Graduandos: A matricula dever\u00e1 ser feita como Aluno Especial P\u00e1gina da Disciplina: – S\u00daMULA Fundamentos. Interse\u00e7\u00f5es de Segmentos de Linha. Particionamento de Pol\u00edgonos. Envolt\u00f3rias Convexas. Diagramas de Voronoi e Triangula\u00e7\u00f5es de Delaunay. Algoritmos de […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":462,"menu_order":189,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/703"}],"collection":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/comments?post=703"}],"version-history":[{"count":3,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/703\/revisions"}],"predecessor-version":[{"id":2496,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/703\/revisions\/2496"}],"up":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/462"}],"wp:attachment":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/media?parent=703"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}