Entrevistas finais

1. Seg: 3 de dezembro, às 15:45 Pedro e João
2. Ter: 4 de dezembro, às 15:00 Rodrigo e Mathias
3. Ter: 4 de dezembro, às 16:15 Nathan
4. Qua: 5 de dezembro, às 10:00 Thiago Estrela e Tiago Napoli
5. Qua: 5 de dezembro, às 14:15 Gabriel Fernandes e Gustavo
6. Qua: 5 de dezembro, às 15:15 Giovana
7. Qui: 6 de dezembro, às 15:30 Breno e Lucas Daher
8. Sex: 7 de dezembro, às 9:30 Vitor Santa Rosa
9. Sex: 7 de dezembro, às 10:00 Andrew e Eduardo Laurentino
10. Sex: 7 de dezembro, às 10:45 Lais
11. Sex: 7 de dezembro, às 15:15 Eduardo Freire Lima
12. Sex: 7 de dezembro, às 16:00 Germano e André
13. Sex: 7 de dezembro, às 16:45 Bruna e Renan
14. Seg: 10 de dezembro, às 10:00 Bia e Igor
15. Seg: 10 de dezembro, às 10:45 Antonio
16. Seg: 10 de dezembro, às 13:30 Jiang e Vinícius
17. Seg: 10 de dezembro, às 14:30 Lucas Moretto
18. Qua: 12 de dezembro, às 15:00 Giovanna e Igor

Possibilidades de Projetos de GeoComp

1. Par de pontos mais próximos [Gabriel Fernandes e Luis Gustavo]
   Implementar o algoritmo força-bruta, um algoritmo aleatorizado descrito na Sec 13.7 do livro de Kleinberg e Tardos (Algorithm Design), o de divisão e conquista, versão bonita que vimos na aula, e um de linha de varredura, com ABBB, que por exemplo aparece brevemente descrito aqui.
2. Todas as interseções de segmentos [Beatriz e Igor Fratel]
   Implementar o algoritmo de força-bruta e o de linha de varredura, com ABBB.
3. Interseção de discos [Eduardo Lima]
   Implementar o algoritmo de linha de varredura para detectar interseção entre dois discos de uma coleção dada de discos. Implementar o algoritmo de força-bruta e o de linha de varredura, com ABBB.
4. Todas as interseções de circunferências [Tiago Napoli e Thiago Estrela]
   Implementar o algoritmo de linha de varredura para detectar todas as interseções entre duas circunferências de uma coleção dada de circunferências. Implementar o algoritmo de força-bruta e o de linha de varredura, com ABBB.
5. Versão discreta do problema do sanduíche de presunto [Giovanna e Pedro]
   Implementar o algoritmo descrito na aula 11 que, dado uma coleção de pontos cada um colorido de azul ou vermelho, encontrar uma reta que separe a coleção em duas contendo o mesmo número de pontos azuis e o mesmo número de pontos vermelhos. A versão linear dele aparece descrita na seção 3 de aqui. Venham conversar comigo pois acho que devemos simplificar algumas coisas nessa implementação.
6. Triangulação de polígonos [Giovana Delfino e Gabriel Russo]
   Implementar o algoritmo de triangulação por remoção de orelhas e o algoritmo de linha de varredura, com ABBB.
7. Partição convexa de polígonos [Bruna e Renan]
   Implementar o algoritmo de Hertel e Mehlhorn, usando o algoritmo de triangulação com linha de varredura, implementado com ABBB.
8. Busca de pontos em janelas ortogonais
   Este tópico é abordado no capítulo 5 do livro de de Berg, van Kreveld, Overmans, Schwarzkopf (dBvKOS). Resolver o caso bidimensional do problema usando uma das EDs lá descritas.
• Resolver o problema com a KD-árvores [Germano e André Nakazawa].
9. Busca de segmentos em janelas ortogonais
   Este tópico é abordado no capítulo 10 do livro de de Berg, van Kreveld, Overmans, Schwarzkopf (dBvKOS). Resolver o caso bidimensional onde os intervalos são paralelos aos eixos, usando as EDs lá descritas.
10. Par de pontos mais próximos online [Antônio]
    Trata-se do seguinte problema: dada uma coleção inicial de pontos, onde são feitas inserções de pontos, manter o tempo todo um par de pontos mais próximos da coleção corrente. Implementar o algoritmo de Schwarz, Smid e Snoeyink [pdf].
11. Plano de locomoção de robôs [Jiang e Vinicius]
    O capítulo 13 de dBvKOS descreve problemas desta classe e alguns algoritmos para resolvê-los. Um dos algoritmos lá descrito usa uma partição em trapézios, semelhante à usada no algoritmo de Lee e Preparata visto em aula. Implementar um destes algoritmos.
12. Grafos de visibilidade [Lucas Moretto]
    O capítulo 15 de dBvKOS discute outros algoritmos para plano de locomoção de robôs, que buscam por rotas mais curtas. Implementar o algoritmo lá descrito.
13. Localização de ponto:
    O site Point Location da Wiki fala de vários algoritmos de point location. A implementação de qualquer um deles vale como projeto.
    • Localização de ponto por decomposição por faixas (slab decomposition) [Breno e Lucas Daher].
14. Visibilidade a partir de um ponto [João Gabriel e Pedro Pereira]
    Implementar um algoritmo de linha de varredura estilo radar, para o exercício 7 da lista 3, usando uma ABBB.
15. Visibilidade do infinito
    Implementar um algoritmo de linha de varredura para a variante do exercício 7 da lista 3 em que queremos a visibilidade a partir do infinito, usando uma ABBB.
16. Remoção de superfície escondida [Lais]
    Dado um conjunto de objetos e a posição de um observador, determinar quais partes de cada objeto estão visíveis. O capítulo 12 de dBvKOS descreve uma ED e um algoritmo para este problema, o algoritmo do pintor. Implementação da versão 2D, ou seja, dada uma coleção de segmentos, o algoritmo monta uma ED e depois aceita como queries um ponto, respondendo quais segmentos da coleção estão visíveis a partir daquele ponto.
17. Diagrama de Voronoi [Andrew e Eduardo Laurentino] [Rodrigo e Mathias]
    
    • Implementar o algoritmo de Fortune, que veremos em aula, para construir o diagrama de Voronoi. Trata-se de um algoritmo de linha de varredura. Use uma ABBB para implementar a linha de varredura.
    • Valendo um bônus, para o primeiro que terminar o acima, construir a triangulação de Delaunay a partir do diagrama de Voronoi.
18. Triangulação de Delaunay [Nathan]
    Implementar o algoritmo descrito no Capítulo 9 do dBvKOS.

19. Triangulação de Delaunay dinâmica [Vitor]
    

Entrevistas

1. Seg: 5 de novembro, às 10:30 Giovanna e Pedro
2. Ter: 6 de novembro, às 11:00 Nathan
3. Ter: 6 de novembro, às 16:30 Giovana Delfino e Gabriel Russo
4. Qui: 8 de novembro, às 13:15 Germano e André
5. Qui: 8 de novembro, às 14:00 Rodrigo Enju e Mathias
6. Qui: 8 de novembro, às 14:45 Igor e Bia
7. Qui: 8 de novembro, às 15:30 Breno e Lucas
8. Seg: 12 de novembro, às 10:15 Antonio Lima
9. Seg: 12 de novembro, às 11:00 Vitor
10. Seg: 12 de novembro, às 13:15 Andrew e Eduardo Laurentino
11. Seg: 12 de novembro, às 14:00 Lucas Moretto
12. Seg: 12 de novembro, às 14:45 Luis Gustavo e Gabriel Fernandes
13. Seg: 12 de novembro, às 15:30 João Gabriel e Pedro Pereira
14. Seg: 12 de novembro, às 16:15 Lais
15. Seg: 12 de novembro, às 17:00 Eduardo Freire
16. Ter: 13 de novembro, às 10:45 Bruna e Renan
17. Qui: 22 de novembro, às 14:00 Thiago e Tiago
18. Qui: 22 de novembro, às 14:45 Vinícius e Jiang
19. Sex: 30 de novembro, às 13:15 Antonio (segunda vez)

Regras

• Tem uma sugestão diferente de projeto? Venha conversar comigo.
• Os projetos podem ser feitos em dupla.
• Os projetos devem ser feitos usando a plataforma Python disponibilizada, originalmente desenvolvida pelo aluno Alexis, a menos que você venha apresentar uma justificativa para implementá-lo em uma outra linguagem ou plataforma. Todos os algoritmos devem ter uma animação que mostre claramente o seu funcionamento.
• Vai haver uma entrevista com cada grupo no final de outubro para ver o andamento das implementações.
• A versão final deverá ser entregue em 2 de dezembro.
• Vai haver uma entrevista final, onde o aluno vai apresentar sua animação e discutir a finalização do desenvolvimento do projeto. Essa entrevista deve ocorrer na primeira semana de dezembro.

O que você deve entregar

• Uma implementação na plataforma do Alexis dos algoritmos pedidos o mais eficiente possível.
• Uma animação dos algoritmos pedidos, nos moldes das animações disponibilizadas na plataforma do Alexis para algoritmos de fecho convexo.
• Um relatório onde você descreve o problema, os algoritmos implementados (se foram vistos em classe, basta dizer quais são), as estruturas de dados utilizadas na sua implementação, uma breve análise do consumo de tempo das suas implementações, e a utilização das cores e o que é mostrado nas suas animações.