Possibilidades de Projetos de GeoComp

1. Par de pontos mais próximos
   Implementar o algoritmo força-bruta, 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. [Rafael Beirigo] [Wanderley]

2. Todas as interseções de segmentos
   Implementar o algoritmo de força-bruta e o de linha de varredura, com ABBB. [Renato Vieira] [Ana Luiza]

3. Área coberta por círculos
   O problema V-circles, resolvido com linha de varredura, com ABBB. [Luís Fernando]

4. Triangulação de polígonos
   Implementar o algoritmo de triangulação por remoção de orelhas e o algoritmo de linha de varredura, com ABBB. [Caio Braz e Gustavo Katague]

5. Partição convexa de polígonos
   Implementar o algoritmo de Hertel e Mehlhorn, usando o algoritmo de triangulação com linha de varredura, implementado com ABBB. [Henrique]

6. Partição convexa de polígonos por diagonais
   Implementar o algoritmo de Keil e Snoeyink, descrito em detalhes aqui. Há uma animação de uma versão anterior do algoritmo aqui e uma do algoritmo aqui. [Renato Parente]

7. 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 a ED lá descrita. [Ricardo Oda]

8. 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. [Renato Lerac]

9. Par de pontos mais próximos online
   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]. [Mariana Pacheco][Santiago]

10. Par de pontos mais próximos dinâmico
    Trata-se do seguinte problema: dada uma coleção inicial de pontos, onde são feitas inserções e remoções de pontos, manter o tempo todo um par de pontos mais próximos da coleção corrente. Implementar o algoritmo de Bespamyatnikh que resolve este problema [pdf]. [Fábio Hirano]

11. Plano de locomoção de robôs
    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
    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. [Igor]

13. Triangulação de polígonos
    Implementar o algoritmo de divisão e conquista de Chazelle, para este problema. Ele aparece descrito aqui. [Diogo]

14. Triangulação de polígonos
    O melhor algoritmo para triangulação de polígonos também deve-se a Chazelle, e usa ideias do artigo acima. Este consome tempo linear para efetuar a tarefa. Ele aparece descrito aqui. [Tássio]

15. 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.
    [Leonardo e Giulia] (algoritmo de Slab Decomposition)
    [André Suzuki e Rafael Parente] (algoritmo que usa triangulação ('triangulation refinement'), que consome espaço linear)

Regras

• Tem uma sugestão diferente de projeto? Venha conversar comigo.
• Para os alunos da graduação, os projetos podem ser feitos em dupla.
• Os projetos devem ser feitos usando a plataforma Python, disponibilizada pelo aluno Alexis. Ou seja, todos os algoritmos devem ter uma animação, que mostre claramente o seu funcionamento.

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.