Qual é realmente um bom problema para sujar as mãos na geometria computacional?

A geometria computacional é uma área que eu acho bastante interessante e gostaria de dedicar cerca de um mês ou dois a um projeto que me apresente isso e me ajude a aprender os principais conceitos.

Qual é uma boa maneira de abordar isso e quais são os principais conceitos que também devem ser introduzidos?

Para misturar as sugestões de Suresh V. e Dave C., pode ser divertido tentar obter evidências experimentais de um problema não resolvido implementando os algoritmos necessários. Por exemplo, agora se sabe que a triangulação de Delaunay não é uma chave ( / 2) [Prosenjit Bose, Luc Devroye, Maarten Löffler, Jack Snoeyink, Vishal Verma: "A proporção de abrangência da triangulação de Delaunay é maior que / 2 ". CCCG 2009 : 165-167.] Você poderia implementar um algoritmo de triangulação de Delaunay e os caminhos mais curtos e tentar determinar experimentalmente qual seria a verdadeira taxa de abrangência. Ou, mais desafiador, tente calcular a complexidade combinatória do diagrama de linhas de Voronoi emπ R$\pi$$\pi$$\mathbb{R}^3$, outro problema não resolvido (e na lista mencionada por Suresh como Problema 3 ).

Embora isso possa ser assustador demais para ser abordado antes de você fazer o que Dave sugere, há uma boa coleção de problemas abertos em geometria computacional mantidos por Joe O'Rourke, Erik Demaine e Joe Mitchell. Eles fornecem um bom instantâneo das principais questões no campo teórico.

Obtenha os problemas de pesquisa de livros em geometria discreta . Leia-o, veja quais problemas você acha interessantes, leia a literatura, resolva e publique.

Aviso: Os problemas deste livro são difíceis. No entanto, é uma excelente introdução aos problemas em aberto no campo e uma boa maneira de aprender sobre o campo.

Victor Klee, em 1973, colocou um problema na proteção de polígonos simples (sensores para proteger uma galeria de arte colocada em seus vértices) que floresceram em centenas de papéis que tratam do que passou a ser conhecido como o Problema da Galeria de Arte. Muitas das idéias básicas em geometria computacional entram em jogo quando se estuda o problema da galeria de arte (coisas como triangulação, decomposição de polígonos em peças com propriedades especiais, gráficos de visibilidade etc.) O livro maravilhosamente bem escrito de Joe O'Rourke ainda serve como um ótimo introdução às idéias e métodos aqui, e o livro está disponível parcial ou totalmente de graça neste site:

http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html

Eu acho que esse é um ótimo ponto de entrada para a geometria computacional.

Jeff Erickson " JeffE " também tem um bom conjunto de indicadores sobre o tópico: http://compgeom.cs.uiuc.edu/~jeffe/compgeom/ . Como ele visita o TCS SE com frequência, ele pode ajudá-lo muito melhor.

Compre um livro como este , implemente os algoritmos e descubra algum exemplo ou projeto pequeno para trabalhar na seção de exercícios. Aqui e aqui estão listas de muitas idéias de projetos. O Google deve revelar muitos outros. Escolha uma que pareça divertida e tente.