Sujet 1 :
trois algorithmes de plus courts chemins
Article de référence
Fast Exact and Approximate Geodesics on Meshes, par V. Surazhsky, T. Surazhsky, D. Kirsanov, S. Gortler et H. Hoppe, SIGGRAPH 2005.Cet article présente trois algorithmes de calcul de plus courts chemins sur des surfaces triangulées :
- un calcul exact de plus court chemin d'un sommet de la surface à tous les autres (l'algorithme dit de MMP, qui avait été proposé il y a déjà longtemps mais dont l'implémentation n'avait jamais été faite tellement il semblait compliqué !) - comme sait le faire Dijkstra;
- un calcul approché, plus rapide, de plus court chemin d'un sommet à tous les autres (algorithme dit de MMP étendu) ;
- un calcul exact de plus court chemin entre deux sommet donnés (algorithme dit de MMP élagué).
Travail demandé
- Implémenter ces trois algorithmes.
- Tester leurs performances (temps de calcul, place mémoire ...) sur diverses surfaces maillées (de tailles diverses, pour des maillages uniformes et non uniformes) et en tirer des conclusions.
- Eventuellement, proposer des améliorations (en particulier, MMP élagué semble compliqué : ne pourrait-on pas faire du Branch and Bound ?).
A lire aussi
- The Discrete Geodesic Problem, par J. Mitchell, M. Mount et C.
Papadimitriou, SIAM Journal of Computing 1987.
L'article d'origine de MMP. Je vous en distribuerai une version imprimée. - Fast Exact and Approximate Geodesic Paths on Meshes, par D. Kirsanov,
S. Gortler et H. Hoppe, rapport de recherche Harvard 2004.
Pour information, plus de détails que dans l'article de SIGGRAPH. Attention, certaines choses ont peut-être été modifiées entre temps.