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