Homotopies optimales en dimension 2 ou le problème de la battue

par Arnaud de Mesmay (Université Grenoble Alpes)

mercredi 28 sept. 2016, 14:00 → 15:00 Europe/Paris

Motivés par des problèmes d'informatique théorique, nous étudions la notion suivante : étant donné un disque muni d'une métrique riemannienne, et une homotopie de son bord vers un point, la hauteur de cette homotopie est la longueur de la plus longue courbe intermédiaire. Une homotopie optimale est une homotopie de hauteur minimale parmi toutes les contractions possibles. Nous montrons qu'il existe toujours une homotopie optimale qui est monotone, c'est-à-dire que les courbes intermédiaires sont toutes simples et chaque point du disque n'est balayé qu'une seule fois. Les techniques utilisées sont assez simples, mais comme nous le verrons c'est un problème étonnamment épineux. En conclusion, nous présentons quelques implications algorithmiques de ce résultat. Travail réalisé avec Erin Chambers, Gregory Chambers, Tim Ophelders et Regina Rotman.