On the complexity of optimal homotopies

E.W. Chambers, A. de Mesmay, T.A.E. Ophelders

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
58 Downloads (Pure)

Abstract

In this article, 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 1 and ϵ on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between 1 and ϵ 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. We prove that Homotopy Height is in the complexity class NP, and the corresponding exponential algorithm is the best one known for this problem. This result builds on a structural theorem on monotonicity of optimal homotopies, which is proved in a companion paper. Then we show that this problem encompasses the Homotopic Fréchet distance problem which we therefore also establish to be in NP, answering a question which has previously been considered in several different settings. We also provide an O(log n)-approximation algorithm for Homotopy Height on surfaces by adapting an earlier algorithm of Har-Peled, Nayyeri, Salvatipour and Sidiropoulos in the planar setting.

Original languageEnglish
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages1121-1134
Number of pages14
ISBN (Electronic)978-1-61197-503-1
DOIs
Publication statusPublished - 7 Jan 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) - Astor Crowne Plaza, New Orleans, United States
Duration: 7 Jan 201810 Jan 2018
Conference number: 29
https://www.siam.org/meetings/da18/

Conference

Conference29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
Abbreviated titleSODA 2018
CountryUnited States
CityNew Orleans
Period7/01/1810/01/18
Internet address

Fingerprint Dive into the research topics of 'On the complexity of optimal homotopies'. Together they form a unique fingerprint.

Cite this