Session A4 - Computational Geometry and Topology
July 11, 15:30 ~ 15:55 - Room B7
On the complexity of optimal homotopies
Arnaud de Mesmay
CNRS, Gipsa-lab, Université Grenoble-Alpes, France - email@example.com
We provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves $\gamma_1$ and $\gamma_2$ on a surface, we want to compute a homotopy between $\gamma_1$ and $\gamma_2$ where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very mathematical questions in quantitative homotopy theory to more practical applications such as similarity measures and graph searching problems.
Our main contribution is a structural theorem showing that there exist optimal homotopies which are very well behaved. It builds on earlier results in Riemannian geometry by Chambers and Liokumovitch and Chambers and Rotman. Leveraging on this theorem allows us to derive new exact and approximation algorithms to compute the homotopy height, and to draw connections with other problems in the same vein like homotopic Fréchet distance.
Joint work with Erin W. Chambers (Saint Louis University, USA), Gregory R. Chambers (Rice University, USA), Tim Ophelders (TU Eindhoven, Netherlands) and Regina Rotman (University of Toronto, Canada).