University of Arkansas Topology Seminar: 5/17/2018

Speaker: Arnaud de Mesmay

Title: On the complexity of optimal homotopies

We provide new structural results and algorithms for the homotopy height between two curves. In broad terms, the homotopy height quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves γ1 and γ2 on a Riemannian surface, we investigate homotopies between γ1 and γ2 where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from theoretical 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 well behaved, i.e., monotone isotopies. 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 in a discrete setting, and to draw connections with other related quantities like the homotopic Fréchet distance.

Based on joint works 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).