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

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

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)39-73
Number of pages35
JournalDiscrete and Computational Geometry
Volume55
Issue number1
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'How to Walk Your Dog in the Mountains with No Magic Leash'. Together they form a unique fingerprint.

Cite this