EADS talk by Arnaud de Mesmay: Complexity of optimal homotopies


On the complexity of optimal homotopies


We provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a combinatorial surface (eg. a planar graph) needs to be stretched to sweep continuously between two positions. The corresponding optimal homotopies are relevant for a wide range of purposes, from very mathematical questions in Riemannian geometry to more practical applications such as similarity measures and graph searching problems.

Our main contribution is a structural theorem showing that there exists 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 and planar cutwidth.

Based on joint work with Erin Chambers, Gregory Chambers, Tim Ophelders and Regina Rotman.