Conference abstracts

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   -

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).

View abstract PDF

FoCM 2017, based on a nodethirtythree design.