Department of
Applied
Mathematics

On the complexity of optimal homotopies

Arnaud de Mesmay

Abstract

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

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 theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes 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, most importantly Homotopic Fréchet distance.