TY - JOUR
T1 - How to Walk Your Dog in the Mountains with No Magic Leash
AU - Har-Peled, Sariel
AU - Nayyeri, Amir
AU - Salavatipour, Mohammad
AU - Sidiropoulos, Anastasios
N1 - Funding Information:
The authors thank Jeff Erickson and Gary Miller for their comments and suggestions. The authors also thank the anonymous referees for their detailed and insightful reviews. S. Har-Peled was partially supported by NSF AF awards CCF-0915984, CCF-1421231, and CCF-1217462. M. Salavatipour was supported by NSERC and Alberta Innovates and also the part of this work was done while visiting Toyota Technological Institute at Chicago. A. Sidiropoulos was supported in part by the NSF grants CCF 1423230 and CAREER 1453472.
Publisher Copyright:
© 2015, Springer Science+Business Media New York.
PY - 2016/1/1
Y1 - 2016/1/1
N2 - We describe a (Formula presented.)-approximation algorithm for computing the homotopic Fréchet distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms were known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a (Formula presented.)-approximation algorithm for computing the minimum height of a homotopy between two curves. No algorithms were previously known for approximating this parameter. Surprisingly, it is not even known if computing either the homotopic Fréchet distance, or the minimum height of a homotopy, is in NP.
AB - We describe a (Formula presented.)-approximation algorithm for computing the homotopic Fréchet distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms were known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a (Formula presented.)-approximation algorithm for computing the minimum height of a homotopy between two curves. No algorithms were previously known for approximating this parameter. Surprisingly, it is not even known if computing either the homotopic Fréchet distance, or the minimum height of a homotopy, is in NP.
KW - Approximation algorithms
KW - Fréchet distance
KW - Homotopy height
UR - http://www.scopus.com/inward/record.url?scp=84953638717&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84953638717&partnerID=8YFLogxK
U2 - 10.1007/s00454-015-9737-3
DO - 10.1007/s00454-015-9737-3
M3 - Article
AN - SCOPUS:84953638717
SN - 0179-5376
VL - 55
SP - 39
EP - 73
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 1
ER -