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 -