Quarto Projeto

1. Embrulho de presente e algoritmo de Graham [Enrique, Felipe, Leonardo, Raphael, Rogério, Ygor]
   Implementar os algoritmos de Jarvis (embrulho de present) e de Graham para o fecho convexo 2D.
2. Incremental e incremental probabilístico
   Implementar o algoritmo incremental para fecho convexo 2D e sua variante probabilística.
3. Quickhull [Daniela, João Pedro, Pedro GF, Ricardo, William]
   Implementar o algoritmo Quickhull para fecho convexo 2D.
4. Mergehull [Bento, Débora, Gabriel ODAA, Giovanne, Matheus SC, Pedro Paulo]
   Implementar o algoritmo Mergehull para fecho convexo 2D.

Terceiro Projeto

1. Partição em polígonos convexos [Matheus SC, Rogério+Ygor, William]
   Implementar o algoritmo de Hertel e Mehlhorn (aula 9). Lembre-se que esse algoritmo requer que seja implementado o algoritmo de Lee e Preparata.
2. Localização de pontos [Gabriel ODAA, João Pedro, Leonardo, Pedro Paulo, Ricardo]
   Implementar os dois algoritmos vistos na aula 10 para localização de ponto: o ray crossing e o winding number.
3. Triangulação de Delaunay [Enrique, Matheus TL, Pedro GF]
   Implementar o algoritmo probabilístico visto na aula 15 para construir a triangulação de Delaunay.
4. Par de pontos mais próximos [Bento e Daniela, Débora, Felipe, Giovanne, Raphael]
   Implementar o algoritmo probabilístico visto na aula 16 para encontrar o par de pontos mais próximos. Este algoritmo aparece descrito na Sec 13.7 do livro de Kleinberg e Tardos (Algorithm Design).

Segundo Projeto: linha de varredura

1. Triangulação de polígonos [Fiorella, Matheus SC, William, Ygor]
   Implementar o algoritmo de Lee e Preparata com uma ABB balanceada a sua escolha.
2. Todas as interseções de uma coleção de segmentos [Bento, Daniela, Felipe, João Pedro, Matheus TL, Ricardo, Rogério]
   Implementar o algoritmo de Bentley e Ottmann com uma ABB balanceada a sua escolha.
3. Todas as interseções de uma coleção de círculos [Gabriel ODAA, Leonardo, Pedro GF]
   Implementar uma adaptação do algoritmo de Bentley e Ottmann com uma ABB balanceada a sua escolha.
Dado um conjunto S de n círculos, cada um dado pelo seu centro e seu raio, determinar todos os pares de círculos de S que se intersectam.
4. Segmentos visíveis a partir de um ponto [Débora, Enrique, Giovanne, Pedro Paulo, Raphael]
   Implementar um algoritmo de linha de varredura com uma ABB balanceada a sua escolha.
Dado um conjunto S de n segmentos de reta disjuntos no plano e um ponto p que não pertence a nenhum dos segmentos de S, determinar todos os segmentos de S que são visíveis a partir de p, isto é, todos os segmentos de S que contém algum ponto q tal que o segmento aberto pq não intersecta nenhum dos segmentos de S.

Primeiro Projeto: aquecimento!

1. Par de pontos mais próximos [Bento, Bruna, Débora, Felipe, Rogério]
   Implementar o algoritmo de divisão e conquista, versão bonita que vimos na aula.
2. Triangulação de polígonos [Daniela, Enrique, Fiorella, Matheus SC, Pedro GF, Rafael T, Ricardo, William]
   Implementar o algoritmo quadrático de triangulação por remoção de orelhas.
3. Par de pontos mais próximos [Fiorella, Gabriel ODAA, Giovanne, João, Raphael]
   Implementar o algoritmo de linha de varredura, com uma ABB simples, que por exemplo aparece brevemente descrito aqui.
4. Detectar interseção de segmentos [Leonardo, Matheus TL, Pedro Paulo, Ygor]
   Implementar o algoritmo de linha de varredura, com ABB simples.

Regras

• Todos os algoritmos devem ter uma animação que mostre claramente o seu funcionamento, como as animações disponibilizadas na plataforma e outras mostradas nas aulas.

O que você deve entregar

• Uma implementação na plataforma disponibilizada do algoritmo escolhido o mais eficiente possível.
• Uma animação do algoritmo escolhido, nos moldes das animações disponibilizadas na plataforma e outras mostradas nas aulas.