Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 39-73 |
Number of pages | 35 |
Journal | Discrete and Computational Geometry |
Volume | 55 |
Issue number | 1 |
DOIs | |
State | Published - Jan 1 2016 |
Keywords
- Approximation algorithms
- Fréchet distance
- Homotopy height
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics