Geometria Computacional

Prof. Pedro J. de Rezende
Primeiro Semestre de 2018

Links rápidos:
Novidades - Docente - Aulas - Conteúdo - Avaliação - Trabalho Teórico - Monografia - Provas
Critérios para Aprovação - Notas - Datas Importantes - Referências Bibliográficas - LaTeX

Novidades Recentes

• Aqui serão colocados avisos importantes. Consulte esta página regularmente.
• A planilha inicial de notas continha um erro de cálculo, mas acaba de ser corrigida. [20180617]
• As notas da Prova 2, dos Trabalhos Teóricos e as Médias Parciais estão disponíveis. [20180617]
• As propostas de Prova 2 estão disponíveis. Mesmo considerando que algumas questões foram reformuladas pelo professor, consultem o responsável pela proposta se precisarem de ajuda para resolvê-las. [20180611] 
• Estendi o prazo para entrega da 1a. Questão da Prova 2 por mais 24hs, a pedido de um aluno. [20180608]
• Sugestões de como preparar uma apresentação estão indicadas. [20180604]
• A matéria coberta pela Prova 2 inclui os tópicos 10. a 16. (que tenham sido dados) da relação abaixo. [20180603]
• Está disponível a 1a. Questão da Prova 2 e um pacote com modelo LaTeX para facilitar sua submissão. [20180603]
• Está disponível uma Lista de Exercícios sobre parte da matéria a ser coberta pela Prova 2. [20180603] 
• As notas da Prova 1 estão disponíveis. [20180425]
• As propostas de Prova 1 estão disponíveis. Mesmo considerando que algumas questões foram reformuladas pelo professor, consultem o responsável pela proposta se precisarem de ajuda para resolvê-las. [20180414] 
• Eis aqui um artigo cujo conteúdo tem relevância para solução de um exercício dessa Lista de Exercícios. [20180411]
• A matéria coberta pela Prova 1 inclui os tópicos 2. a 10. (até Diagramas de Voronoi) da relação abaixo. [20180405] 
• Está disponível a 1a. Questão da Prova 1 e um pacote com modelo LaTeX para facilitar sua submissão. [20180405] 
• Está disponível uma Lista de Exercícios sobre parte da matéria a ser coberta pela Prova 1. [20180404]
• Alguns exemplos de textos de trabalhos teóricos de semestres anteriores estão indicados. [20180404]
• As aulas terão início no dia 27/02. [20180204]

Docente

	Prof. Pedro J. de Rezende
	Sala IC-29, http://www.ic.unicamp.br/~rezende, (19) 3521-5860,

Aulas e Atendimento

	As aulas serão às terças-feiras e às quintas-feiras das 16h00-18h00 na sala IC-351.
	O professor dará atendimento aos alunos logo após cada aula ou por agendamento individual por email, a pedido.

Conteúdo

Esses tópicos, ou sua ordem, poderão ser alterados durante o semestre, conforme o andamento da disciplina.
A relação abaixo corresponde aos tópicos que foram cobertos na última vez em que esta disciplina foi oferecida.

1. Pré-requisitos
   1. Crescimento assintótico de funções (Graduação)
   2. Complexidade computacional (Graduação)
   3. Estruturas de dados (Graduação)
   4. Algoritmos de ordenação (Graduação)
   5. Algoritmos de busca (Graduação)
   6. Geometria Analítica (Ensino Médio)
2. Modelos computacionais [dRS94 1.3-1.7] e [PS85 1.4, 5.2] [notas complementares] [C96 8.1] (Aula 1) (Aula 2)
3. Cotas inferiores e reducibilidade [dRS94 1.7] e [notas] e [exercícios] [C96 8.2, 8.3.1] (Aula 3) (Aula 4)

   Convém ler também essas notas de Jeffe Erickson levemente corrigidas.

4. Problemas Geométricos Elementares [dRS94 3.1-3.2] (Aula 5)
5. Trabalhando com Polígonos [dRS94 3.3-3.5] (Aula 6)
6. Problemas de Convexidade [dRS94 4.1-4.3.5] e [PS85 3.1-3.3.5, 4.1.2, 4.2.3] (Aula 7) (Aula 8) (Aula 9)
7. Estrutura de dados DCEL [Slides] (Aula 9)
8. Problemas de Consulta Geométrica (Localização de Pontos) [Slides] [PS85 2.2 a 2.2.2.2] (Aula 10)
9. Problemas de Consulta Geométrica (Busca por Amplitude) [Slides] [PS85 2.3-2.3.2] (Aula 11)
10. Problemas de Proximidade [PS85 5.1-5.6, 6.1, 6.3.1, 6.4], [dBvKOS97 7.1-7.4] (Aula 12...)

    	Slides com introdução a Diagramas de Voronoi, usados em classe.
    	Slides sobre Diagramas de Voronoi, Triangulação de Delaunay e extensões, usados em classe.
    	* Vários softwares interessantes sobre diagramas de Voronoi (em particular, Voroglide); * um GIF dinâmico; * animações do algoritmo de Steve Fortune:   - Rashid Bin Muhamad   - Raymond Hill   - Eduard Zhang Material adicional de leitura: Slides (de Vera Sacristán) com algoritmos para construção de Diagramas de Voronoi; página sobre o algoritmo de divisão e conquista com ótimas ilustrações.
    	Leitura adicional (contém muito mais do que vimos em classe) sobre Triangulações de Delaunay.

11. Triangulação [PS85 6.2, 6.2.2], [O'R93 1.2, 2.1-2.2] e [dBvKOS97 3.2-3.3]

    Slides sobre Triangulação, usados em classe. (n-3ª)

12. Problemas de Intersecção [PS85 7.1-7.2], [dBvKOS97 2.1]

    	Interseção de Polígonos Convexos, Estrelados, Simples
    	Teste de Simplicidade
    	Interseções de Segmentos (intervalos, segmentos horizontais, horizontais+verticais) Detecção e enumeração (Slides sobre Intersecções que utilizamos em classe.) (n-3ª)
    	Guia de estudo na forma de perguntas que utilizamos em classe. (n-2ª)
    	Separabilidade de dois conjuntos de pontos
    	Separabilidade de dois polígonos convexos
    	Interseção de meios-planos
    	Planaridade de um desenho de grafo
    	Interseção de circunferências

13. Problemas de Caminhos Mínimos [O'R93 8.1-8.2] e [dBvKOS97 15.1-15.2]

    	Grafos de visibilidade e suas aplicações a determinação de caminhos mínimos.
    	Caminhos mínimos no interior de polígonos simples. (Slides sobre Caminhos Mínimos que utilizamos em classe. Leitura adicional. Survey sobre este tópico = seções 1.1, 2.1, 3.1.)
    	Caminhos mínimos na presença de obstáculos poligonais. [Este tópico poderá ser omitido.]
    	Métricas não euclidianas. [Este tópico poderá ser omitido.]

14. Arranjos de retas [O'R93 6.1-6.3, 6.5]* e [dBvKOS97 8.2-8.3]* [Este tópico poderá ser omitido.]

    	Arranjos de retas no plano.  [Este tópico poderá ser omitido.]
    	Dualidade e aplicações (incl. grafo de visibilidade).  [Este tópico poderá ser omitido.]

15. Separabilidade [O'R93 8.7]

    Separabilidade de segmentos de retas, polígonos convexos, NP-dificuldade do problema geral. (Slides sobre Separabilidade que utilizamos em classe.)

16. Problemas de Galeria de Arte [O'R87 pgs: 1-9 36-47, 116-123, 217-219, 228-231, 239-242]

    Teorema de Fisk (Slides usados em classe.), NP-Completude do problema da minimização. (Slides usados em classe.)

17. Problemas de Galeria de Arte

    Algoritmo exato via cobertura de conjuntos: estratégias eficientes para instâncias grandes. (Slides usados em classe e o correspondente artigo.)

Avaliação

Haverá um trabalho teórico e duas provas como parte da avaliação obrigatória desta disciplina.

Cada estudante fará um trabalho teórico (TT) em profundidade a respeito de um tópico de natureza geométrica escolhido em comum acordo com o professor.

O tópico deverá corresponder ao estudo de um problema aberto (por exemplo, desta lista) ou tópico similar mediante concordância do professor, e deverá incluir:

	Leitura dos artigos de referências relevantes ao problema;
	Aprofundamento no estado da arte das tentativas de solução existentes na literatura.

Antes de fazer sua escolha, consulte a relação dos tópicos já escolhidos pelos seus colegas.

Uma monografia para o trabalho (de 6 a 10 páginas, preferencialmente em LaTeX) deverá ser entregue para avaliação e deverá conter:

1. uma clara descrição do problema;

2. uma exposição resumida do conteúdo das referências que foram lidas sobre o problema;

3. um sumário dos avanços já obtidos para a solução do problema (incluindo os casos particulares já solucionados);

4. uma conclusão sobre as dificuldades inerentes ao problema, segundo a sua ótica;

5. uma proposta de abordagem que você acredita que poderia trazer algum avanço à solução do problema.

Ao submeter sua monografia, envie por e-mail para , um tgz ou zip de um diretório que contenha o PDF do seu trabalho e todos os arquivos fontes (em LaTeX) do trabalho.

Você pode e deve consultar livremente todo material impresso ou digitalmente disponível podendo incluir em sua monografia:

	citações interpretadas (e traduzidas) por você devidamente referenciadas;
	citações ipsis litteris desde que devidamente sinaladas com aspas e referenciadas;
	ilustrações obtidas de outras fontes desde que devidamente referenciadas.

Para obter cópia dos artigos listados nas referências, você pode se beneficiar de vários repositórios de artigos disponíveis na WEB, incluindo (acesse de um IP da Unicamp): Portal de Periódicos da Capes; JSTOR; ACM Digital Library; IEEE Xplore; etc.

Com um zeloso cuidado em fazer suas citações corretamente, você evitará qualquer similitude imprópria e potencial libelo de plágio.

Como sugestão de modelo para sua monografia, consulte os seguintes exemplos de textos de trabalhos teóricos de semestres anteriores: exemplo1, exemplo2, exemplo3.

Cada estudante fará uma apresentação oral (cuja duração deverá ser de até 30 mins) para a classe e o professor sobre seu trabalho. A ordem das apresentações será estabelecida em classe oportunamente.

A avaliação desse trabalho (monografia + apresentação) corresponderá a 0,4 da nota do semestre.

Relação dos tópicos já escolhidos

Os seguintes alunos já escolheram os tópicos para seus trabalhos:

Aluno	Problema Aberto/Tema Escolhido
Natanael Ramos	Maximum Area Polygonalization
Augusto Bernardi	Shortest paths in line arrangements - http://jeffe.cs.illinois.edu/open/algo.html#shortpath
Guilherme Valarini	Dynamic Planar Nearest Neighbors - http://cs.smith.edu/~jorourke/TOPP/P63.html#Problem.63
Allan S. Barboza	Convex Quadrangulations of Bichromatic Point Sets - https://mat-web.upc.edu/people/carlos.seara/data/ publications/internationalConferences/EuroCG-17_paper_23.pdf

Provas

Haverá 2 provas (P1, P2) durante o semestre nas datas indicadas abaixo.

Os pesos serão 0,2 e 0,4 da nota do semestre, para a 1a. e a 2a. provas, respectivamente. As provas serão tomadas em classe durante horário de aula, constituindo-se em trabalho individual.

Não serão ministradas provas antecipadas nem de reposição. O não comparecimento à primeira prova, se justificado de modo considerado satisfatório pelo professor, será sanado pela substituição daquela nota pela da segunda prova, a qual é obrigatória.

Esta disciplina não prevê Exame final (tanto para MO619 quanto para MC948).

Aviso: Qualquer tentativa de cola ou fraude, detectada durante uma prova ou posteriormente, implicará nota zero naquela prova e na aplicação das sanções regimentais previstas.

Como as notas de P1, P2 e TT serão entre 0,0 e 10,0, a Média Semestral (MS) será, portanto, calculada pela expressão:

As Menções Finais (MF) para MO619 serão obtidas pelo seguinte mapeamento da Média Semestral, MS:

MS ≥ 9,0 => MF:=A, MS entre [7,5; 9,0) => MF:=B, MS entre [6,0; 7,5) => MF:=C, MS entre [0,0; 6,0) => MF:=D.

A Tabela de Notas está disponível aqui.

Cada estudante que se interessar por realizar um opcional trabalho prático (de implementação, testes e análise de resultados) sobre algum problema geométrico deverá discutir essa possibilidade com o professor até o dia 03 de maio, impreterivelmente. Note a última palavra: impreterivelmente.

Os trabalhos práticos serão avaliados e poderão acrescer a Média Semestral (MS) em até 1,0 (um) ponto.

Datas importantes

Referências Bibliográficas

Vários livros dentre os seguintes estão disponíveis na Biblioteca do IMECC para referência bibliográfica. Não há um livro texto para esta disciplina, mas praticamente todo o material a ser visto pode ser encontrado num dos seguintes: [dRS94], [PS85], [dBvKOS97] e [O’R93]. À medida que cada tópico vá sendo coberto, o professor indicará qual referência melhor se aplica. Certos tópicos de geometria computacional poderão ser retirados de outros livros, especialmente: [O’R87], [Mul93], [Ede87], [Sto91], [Tou85] e [Kle89]. Para uma revisão de análise de algoritmos, recomenda-se: [Man89], [Sed83], [CLR90] e [AHU74]. Uma abordagem interessante para quando se precisar rever estruturas de dados é a do livro [SW].

	[AHU74] A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.
	[AL93] S. G. Akl and K. A. Lyons. Parallel Computational Geometry. Prentice-Hall, 1993.
	[CF91] P.C. Carvalho and L.H. Figueiredo. Introdução à Geometria Computacional. 18o. Colóquio Brasileiro de Matemática. Instituto de Matemática Pura e Aplicada, Rio de Janeiro, RJ, Brazil, 1991.
	[C96] J.  Chen, Computational Geometry, Methods and Applications, 1996.
	[CLR90] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press, Cambridge, Mass., 1990.
	[dBvKOS97] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, New York, 1997.
	[dRS94] P. J. de Rezende and J. Stolfi. Fundamentos de Geometria Computacional. IX Escola de Computação. Universidade Federal de Pernambuco, 250 pp., 1994.
	[Ede87] H. Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Heidelberg, West Germany, 1987.
	[GJ79] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, 1979.
	[Kle89] R. Klein. Concrete and Abstract Voronoi Diagrams, volume 400 of Lecture Notes in Computer Science. Springer-Verlag, 1989.
	[Man89] U. Manber. Algorithms: A Creative Approach. Addison-Wesley, Reading, MA.
	[Mul93] K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, New York, 1993.
	[O’R87] J. O’Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987.
	[O’R93] J. O’Rourke. Computational Geometry in C. Cambridge University Press, 1993.
	[PS85] F. P. Preparata and M. I. Shamos. Computational Geometry. Springer-Verlag, Berlin, 1985.
	[Sed83] R. Sedgewick. Algorithms. Addison-Wesley, Reading, MA, 1983.
	[Sto91] J. Stolfi. Oriented Projective Geometry: A Framework for Geometric Computations. Academic Press, 1991.
	[SW] D. F. Stubbs and N. W. Webre. Data Structures with Abstract Data Types and Pascal. Brooks/Cole.
	[Tou85] G. T. Toussaint, editor. Computational Geometry. North-Holland, Amsterdam, Netherlands, 1985.

Wikipedia tem também uma longa lista de livros da área.

Conferências/Simpósios com artigos em Geometria Computacional

Muitos artigos que eventualmente aparecem em revistas especializadas (journals) têm versões preliminares publicadas em conferências ou simpósios da área e podem assim ser conhecidos meses (ou até anos) antes de sua publicação final. Outros artigos de grande relevância podem ser apresentados nesses eventos sem serem posteriormente submetidos a revistas. Como a UNICAMP tem acesso (via seus IPs institucionais) a vários sites de publicações eletrônicas (especialmente ACM e IEEE) muitos dos anais (proceedings) podem ser obtidos em PDF.

Consulte os links seguintes para uma relação muito completa de conferências dedicadas a (ou com trilhas em) geometria computacional:

	Lista de conferências de Erik Demaine.
	Lista de eventos de Joe Mitchell (inclui também conferências em áreas próximas).

Problemas Abertos em Geometria Computacional

Há várias possíveis fontes de problemas abertos em geometria computacional. As seguintes referências formam um bom ponto de partida:

	The Open Problems Project de Demaine, Mitchell, O'Rourke.
	Problemas abertos de David Eppstein.
	Problemas abertos de Jeff Erickson (veja também os links dessa página).

Links úteis sobre Geometria Computacional

	Links para diversas páginas sobre geometria computacional. [Se você encontrar outras (de equivalente grau de relevância) que não constam ali, me avise por e-mail: .]
	Mais uma página com links para diversas outras páginas sobre geometria computacional.
	Links para software de geometria computacional na Web.

Giving Technical Talks

Onde aprender a usar LaTeX

Existem vários livros, apostilas e tutoriais online sobre LaTeX. Em particular, recomendo:

Document Preparation with Latex, de Budgen & Nelson.

	Getting Started with Latex, de Wilkins.
	A Simplified Introduction to LaTeX, de Greenberg.
	[Em português] A não tão pequena introdução da LaTeX 2e, de Oetiker, Partl, Hyna & Schlegl.