Home Bookmarks Papers Blog

How to Walk Your Dog in the Mountains with No Magic Leash

Sariel Har-Peled, Amir Nayyeri, Mohammad Salavatipour, and Anastasios Sidiropoulos.


We describe a O(log n)-approximation algorithm for computing the homotopic Frechet 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 Frechet distance, or the minimum height of a homotopy, is in NP.
PDF.
Last modified: Sat Dec 3 16:35:22 CST 2011