TY - GEN
T1 - How to walk your dog in the mountains with no magic leash
AU - Har-Peled, Sariel
AU - Nayyeri, Amir
AU - Sidiropoulos, Anastasios
AU - Salavatipour, Mohammad
PY - 2012
Y1 - 2012
N2 - We describe a O(log n)-approximation algorithm for computing the homotopic Frechét distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms where known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a O(log n)-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 Frechét distance, or the minimum height of a homotopy, is in NP.
AB - We describe a O(log n)-approximation algorithm for computing the homotopic Frechét distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms where known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a O(log n)-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 Frechét distance, or the minimum height of a homotopy, is in NP.
KW - Approximation algorithms
KW - Frechét distance
UR - http://www.scopus.com/inward/record.url?scp=84863901950&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84863901950&partnerID=8YFLogxK
U2 - 10.1145/2261250.2261269
DO - 10.1145/2261250.2261269
M3 - Conference contribution
AN - SCOPUS:84863901950
SN - 9781450312998
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 121
EP - 130
BT - Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012
T2 - 28th Annual Symposuim on Computational Geometry, SCG 2012
Y2 - 17 June 2012 through 20 June 2012
ER -