Est
Projetos de GeoComp
Preferivelmente deve ser usada a plataforma do projeto do Alexis.
Possibilidades de Projetos de GeoComp
- Par de pontos mais próximos
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.
- Todas as interseções de segmentos [Bárbara]
Implementar o algoritmo de força-bruta e o de linha de varredura, com ABBB.
- Área coberta por círculos
O problema V-circles,
resolvido com linha de varredura, com ABBB. Acho que é possível implementar esse algoritmo de forma
que o resultado seja um algoritmo que consome O(n^2 log n). Podemos conversar para esclarecer como
obter este consumo de tempo. Uma outra possibilidade é implementar o algoritmo de Imai, Iri e Murota,
que usa diagrama de Laguerre (uma variação do diagrama de Voronoi) e está descrito
aqui.
- Triangulação de polígonos [Caio]
Implementar o algoritmo de triangulação por remoção de orelhas
e o algoritmo de linha de varredura, com ABBB.
- Partição convexa de polígonos [Mateus]
Implementar o algoritmo de Hertel e Mehlhorn, usando o algoritmo
de triangulação com linha de varredura, implementado com ABBB.
- 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.
- Busca de pontos em janelas ortogonais [Renzo] [Rafael e Stefano]
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.
- 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.
- Par de pontos mais próximos online [Edênis]
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].
- Par de pontos mais próximos dinâmico [José Rodrigues]
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].
Este algoritmo utiliza uma ED de Bent, Sleator e Tarjan [pdf].
- Plano de locomoção de robôs [Karina]
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.
- Grafos de visibilidade [Victor]
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.
- Triangulação de polígonos [Henrique Stagni]
Implementar o algoritmo de divisão e conquista de Chazelle,
para este problema. Ele aparece descrito aqui.
- Localização de ponto: [Henrique Coelho]
O site Point
Location da Wiki fala de vários algoritmos de point
location. A implementação de qualquer um deles vale como
projeto.
- Visibilidade a partir de um ponto [Daniel Paulino e Felipe Yamaguti]
Implementar um algoritmo de linha de varredura estilo radar, para o exercício 7 da lista 3,
usando uma ABBB.
- Visibilidade do infinito [Antonio]
Implementar um algoritmo de linha de varredura estilo radar, para o exercício 7 da lista 3,
usando uma ABBB.
- Diagrama de Voronoi [Felipe Blassioli]
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.
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, 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.
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.
Last modified: Fri Sep 26 09:29:29 BRT 2014