On the complexity of optimal homotopies

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)
38 Downloads (Pure)

Uittreksel



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 γ2 on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy 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 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.



Originele taal-2Engels
TitelProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Pagina's1121-1134
Aantal pagina's14
ISBN van elektronische versie978-1-61197-503-1
DOI's
StatusGepubliceerd - 7 jan 2018
Evenement29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) - Astor Crowne Plaza, New Orleans, Verenigde Staten van Amerika
Duur: 7 jan 201810 jan 2018
Congresnummer: 29
https://www.siam.org/meetings/da18/

Congres

Congres29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
Verkorte titelSODA 2018
LandVerenigde Staten van Amerika
StadNew Orleans
Periode7/01/1810/01/18
Internet adres

Vingerafdruk

Homotopy
Curve
Graph Searching
Homotopy Theory
Complexity Classes
Sweep
Similarity Measure
Monotonicity
Approximation Algorithms
Quantify
Mesh
Computing
Term
Theorem
Range of data

Citeer dit

Chambers, E. W., de Mesmay, A., & Ophelders, T. A. E. (2018). On the complexity of optimal homotopies. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana (blz. 1121-1134). New York: Association for Computing Machinery, Inc. https://doi.org/10.1137/1.9781611975031.73
Chambers, E.W. ; de Mesmay, A. ; Ophelders, T.A.E. / On the complexity of optimal homotopies. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana. New York : Association for Computing Machinery, Inc, 2018. blz. 1121-1134
@inproceedings{4de7f23de5664b90bfbdc0f2aaa5b1db,
title = "On the complexity of optimal homotopies",
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 γ2 on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy 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 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{\'e}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.",
author = "E.W. Chambers and {de Mesmay}, A. and T.A.E. Ophelders",
year = "2018",
month = "1",
day = "7",
doi = "10.1137/1.9781611975031.73",
language = "English",
pages = "1121--1134",
booktitle = "Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana",
publisher = "Association for Computing Machinery, Inc",
address = "United States",

}

Chambers, EW, de Mesmay, A & Ophelders, TAE 2018, On the complexity of optimal homotopies. in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana. Association for Computing Machinery, Inc, New York, blz. 1121-1134, New Orleans, Verenigde Staten van Amerika, 7/01/18. https://doi.org/10.1137/1.9781611975031.73

On the complexity of optimal homotopies. / Chambers, E.W.; de Mesmay, A.; Ophelders, T.A.E.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana. New York : Association for Computing Machinery, Inc, 2018. blz. 1121-1134.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

TY - GEN

T1 - On the complexity of optimal homotopies

AU - Chambers, E.W.

AU - de Mesmay, A.

AU - Ophelders, T.A.E.

PY - 2018/1/7

Y1 - 2018/1/7

N2 - 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 γ2 on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy 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 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.

AB - 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 γ2 on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy 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 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.

U2 - 10.1137/1.9781611975031.73

DO - 10.1137/1.9781611975031.73

M3 - Conference contribution

SP - 1121

EP - 1134

BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana

PB - Association for Computing Machinery, Inc

CY - New York

ER -

Chambers EW, de Mesmay A, Ophelders TAE. On the complexity of optimal homotopies. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana. New York: Association for Computing Machinery, Inc. 2018. blz. 1121-1134 https://doi.org/10.1137/1.9781611975031.73