Quel est un très bon problème pour se salir les mains en géométrie numérique?

12

La géométrie informatique est un domaine que je trouve assez intéressant, et j'aimerais consacrer environ un mois ou deux à un projet qui va m'initier à cela et m'aider à apprendre les concepts clés.

Quelle est la bonne façon d'aborder cela et quels sont les concepts clés dont je devrais être sûr que je suis également présenté?


la source
2
(la langue fermement en joue): Lisez le Geomblog !! ( geomblog.blogspot.com )
Suresh Venkat
Vous recherchez un projet de programmation, un projet théorique ou un mélange des deux?
James King

Réponses:

8

Pour mélanger les suggestions de Suresh V. et Dave C., il pourrait être amusant d'essayer d'obtenir des preuves expérimentales sur un problème non résolu en mettant en œuvre les algorithmes nécessaires. Par exemple, on sait maintenant que la triangulation de Delaunay n'est pas une clé ( / 2) [Prosenjit Bose, Luc Devroye, Maarten Löffler, Jack Snoeyink, Vishal Verma: "Le rapport d'étendue de la triangulation de Delaunay est supérieur à / 2. " CCCG 2009 : 165-167.] Vous pouvez implémenter un algorithme de triangulation de Delaunay et les chemins les plus courts, et essayer de déterminer expérimentalement quel pourrait être le véritable rapport d'étalement. Ou, plus difficile, essayez de calculer la complexité combinatoire du diagramme de Voronoï des lignes dansπ R 3ππR3, un autre problème non résolu (et dans la liste que Suresh mentionne comme problème 3. )

Joseph O'Rourke
la source
2
Cette dernière suggestion est MOYENNE!
Jeffε
1
Oui, "plus difficile" est un euphémisme! Caveat emptor!
Joseph O'Rourke
7

Bien que cela puisse être trop intimidant pour vous lancer avant de faire comme le suggère Dave, il existe une belle collection de problèmes ouverts en géométrie computationnelle maintenus par Joe O'Rourke, Erik Demaine et Joe Mitchell. Celles-ci fournissent un bon aperçu des questions fondamentales dans le domaine théorique.

Suresh Venkat
la source
6

Obtenez les problèmes de recherche de livres en géométrie discrète . Lisez-le, voyez quels problèmes vous intéressent, lisez la littérature, résolvez et publiez.

Avertissement: les problèmes de ce livre sont difficiles. Cependant, c'est une excellente introduction aux problèmes ouverts sur le terrain et un bon moyen d'en apprendre davantage sur le terrain.

Sariel Har-Peled
la source
5

Victor Klee en 1973 a posé un problème de protection des polygones simples (capteurs pour protéger une galerie d'art placée à ses sommets) qui s'est transformé en centaines de documents traitant de ce qui est devenu le problème de la galerie d'art. Beaucoup d'idées de base en géométrie computationnelle entrent en jeu lors de l'étude du problème de la galerie d'art (des choses telles que la triangulation, la décomposition des polygones en morceaux avec des propriétés spéciales, des graphiques de visibilité, etc.) Le livre merveilleusement bien écrit de Joe O'Rourke sert toujours de grand introduction aux idées et méthodes ici, et le livre est disponible en partie ou en totalité gratuitement sur ce site web:

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

Je pense que c'est un excellent point d'entrée dans la géométrie informatique.

Joseph Malkevitch
la source
1
Merci, Joe! Et si je peux ajouter, il reste ici des problèmes non résolus qui pourraient correspondre à ma suggestion de diriger votre énergie vers un problème ouvert. Cela le rend plus excitant. :-)
Joseph O'Rourke
4

Jeff Erickson " JeffE " a également un bel ensemble de pointeurs sur le sujet: http://compgeom.cs.uiuc.edu/~jeffe/compgeom/ . Comme il visite fréquemment TCS SE, il peut vous aider beaucoup mieux.

MS Dousti
la source
Prudent! Je n'ai pas mis à jour cet ensemble de pages Web depuis plus d'une décennie !!
Jeffε
4

Achetez un livre comme celui-ci , implémentez les algorithmes et découvrez un exemple ou un petit projet sur lequel travailler dans la section des exercices. Voici et voici des listes de nombreuses idées de projets. Google devrait en révéler bien d'autres. Choisissez celui qui semble amusant et allez-y.

Dave Clarke
la source