Test d'homotopie entre courbes sur les surfaces combinatoires

De Ensiwiki
Aller à : navigation, rechercher


Test d'homotopie entre courbes sur les surfaces combinatoires

Labo GIPSA-Lab
Equipe AGPIG
Encadrants Francis.Lazarus@gipsa-lab.grenoble-inp.fr

Thème général

topologie algorithmique et plus précisément : Implémentation d'un algorithme pour le test d'homotopie entre courbes sur les surfaces combinatoires.

Compétences attendues

Algorithmique des graphes, programmation C++, si possible quelques notion de topologie

Contexte du travail

Ce travail s'inscrit dans le cadre de l'ANR GATO [1] de développement d'une bibliothèque C++ intégrée à CGAL [2].

Sujet

Comprendre et développer en C++ l'algorithme de test d'homotopie décrit dans les articles suivants :

- On the homotopy test on surfaces. Francis Lazarus and Julien Rivaud. proc. IEEE Symposium on Foundations of Computer Science (FOCS), pp. 440-449, 2012. - Transforming curves on surfaces redux. Erickson, J. & Whittelsey, K. Proc. 24rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2013

Résultats attendus

Un programme qui permet de décider si deux chemins fermés dans une surface combinatoire peuvent être déformés continûment l'un en l'autre.