CI1338 / CI7061

Geometria Computacional / Tópicos em Geometria Computacional

2023/1

Horário: 3as e 5as, 13:30

Sala de aula: PC-03

Lista de e-mails: https://listas.inf.ufpr.br/cgi-bin/mailman/listinfo/geometria

Ao inscrever-se você receberá mensagem pedindo confirmação. Só após a confirmação você estará efetivamente inscrito.

A lista só aceita mensagens enviadas a partir do endereço com o qual você se inscreveu.

Você pode inscrever mais de um endereço.

Objetivo

Apresentar os conceitos fundamentais de Geometria Computacional e algumas técnicas para a resolução de problemas com mais de uma dimensões.

Avaliação

Uma prova e trabalhos práticos envolvendo a solução algorítmica de problemas usando as técnicas vistas na disciplina.

Veja as notas aqui!

Calendário

Início: 21/03/2023
Entrega do 1o trabalho: 17/04/2023 (até 23:59)

Notas e Avaliação

Veja suas notas aqui.

Material de leitura e exercícios

Os números do tipo "[nn]" se referem a itens da bibliografia.

Usaremos o livro Computational Geometry: Algorithms and Applications [1] como livro texto.

Link temporário com os textos a serem usados.
21/03/2023: Apresentação da disciplina
23/03/2023: Introdução (Cap. 1)
28/03/2023: Introdução (Cap. 1)
30/03/2023: Intersecção de segmentos (Cap. 2)
04/04/2023: Subdivisão planar - DCEL (Cap. 2)
06/04/2023: Malha de triângulos / simplexos
11/04/2023: Triangulação de polígonos (Cap. 3)
13/04/2023: Triangulação de polígonos (Cap. 3)
18/04/2023: Busca por faixas ortogonais (Cap. 5)
- Seções 5.1 a 5.3 são necessárias;
- Seções 5.4 e 5.5 são interessantes, mas opcionais;
- Seção 5.6 é muito interessante, mas pode ser vista como extra.
20/04/2023: Busca por faixas ortogonais (Cap. 5)
25/04/2023: Localização de pontos (Cap. 6)
- Seções 6.1 a 6.3 são necessárias;
- As demais são opcionais.
27/04/2023: Seleção de segmentos em uma janela retangular (Cap. 10)
02/05/2023: Seleção de segmentos em uma janela retangular (Cap. 10)
04/05/2023: Diagrama de Voronoi (Cap. 7)
09/05/2023: Diagrama de Voronoi (Cap. 7)
- Seções 7.1 e 7.2 são necessárias;
- As demais são opcionais.
11/05/2023: Triangulação de Delaunay (Cap. 9)
- Seções 9.1 a 9.3 são necessárias;
- Seções 9.4 e 9.5 são muito interessantes, mas podem ser vistas como extras.
16/05/2023: Fecho convexo (Cap. 11)
- Seções 11.1 e 11.2 são necessárias;
- Seções 11.3 a 11.5 são interessantes, mas opcionais.
18/05/2023: BSP (Cap. 12)
- Seções 12.1 a 12.3 e 12.5 são necessárias;
- Seções 12.4 é interessantes, mas opcional.
23/05/2023: Movimentando um robô (Cap. 13)
25/05/2023: Quadtree (Cap. 14)
...
04/07/2023: Prova final

Bibliografia

[1] Computational Geometry: Algorithms and Applications. M. de Berg, M. van Kreveld, M. Overmars, O. Cheong. Springer, 3a. Ed. 2008.

[2] Computational Geometry: An Introduction. F. P. Preparata, M. I. Shamos. Springer-Verlag, 1985.

[3] Introdução à Geometria Computacional. L. H. de Figueiredo, P. C. P. Carvalho. 18o Colóquio Brasileiro de Matemática. IMPA. 1991.

[4] Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein. 2009.

[5] Algorithm Design. Jon Kleinberg e Éva Tardos. 2005.

Bibliografia complementar

[6] Algorithmic Geometry. J-D. Boissonat, M. Yvinec. Cambridge University Press, 1998.

[7] [Reconhecimento de Padrões em Subdivisões Planares http://dspace.c3sl.ufpr.br:8080/dspace/handle/1884/1899]. Pedro Ribeiro de Andrade Neto. Dissertação de mestrado, PPGInf/UFPR, dezembro 2004.

[8] Estruturas de Dados. P.A.S. Veloso, C.S. Santos, P.A. Azeredo, A.L. Furtado. Editora Campus, Rio de Janeiro, RJ, 1986.

[9] [An Introduction to Topology: The Classification theorem for Surfaces By E. C. Zeeman https://www.maths.ed.ac.uk/~v1ranick/surgery/zeeman.pdf]

[Original (parece) http://math.iisc.ernet.in/~subhojoy/public_html/Zeeman.pdf]
[An Extension of Zeeman’s an Introductionto Topology, Jennifer Liu http://ccs.math.ucsb.edu/senior-thesis/JenniferLiu.pdf]

[10] The Algorithm Design Manual. Skiena. Springer, 1998.

[11] Algorithms. R. Sedgewick. Addison-Wesley, Reading, Massachusetts, 1983.

[12] Data Structures and Algorithms. A.V. Aho, J.E. Hopcroft, J.D. Ullman. Addison-Wesley, Reading, Massachusetts, 1983.

[13] Algorithms and Data Structures. N. Wirth. Prentice-Hall, 1986 (Tradução: Algoritmos e Estruturas de Dados. Prentice-Hall do Brasil Ltda, 1989).

[14] The Art of Computer Programming vol. 1, D.E. Knuth.

[15] The Art of Computer Programming vol. 3, D.E. Knuth.

[16] The Art of Computer Programming vol. 4, D.E. Knuth.

[17] Competitive Programming 3: The New Lower Bound of Programming Contests (Steven Halim e Felix Halim)

[18] Handbook of Discrete and Computational Geometry —Third Edition— edited by Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth CRC Press LLC, Boca Raton, FL, 2017. ISBN 978-1498711395 (68 chapters, xix + 1928 pages)

[19] Handbook of computational geometry. J.-R. Sack and J. Urrutia (Eds.). 2000. North-Holland Publishing Co., NLD.