How to walk your dog in the mountains with no magic leash

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012
Pages121-130
Number of pages10
DOIs
StatePublished - Jul 23 2012
Event28th Annual Symposuim on Computational Geometry, SCG 2012 - Chapel Hill, NC, United States
Duration: Jun 17 2012Jun 20 2012

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other28th Annual Symposuim on Computational Geometry, SCG 2012
CountryUnited States
CityChapel Hill, NC
Period6/17/126/20/12

    Fingerprint

Keywords

  • Approximation algorithms
  • Frechét distance

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Cite this

Har-Peled, S., Nayyeri, A., Sidiropoulos, A., & Salavatipour, M. (2012). How to walk your dog in the mountains with no magic leash. In Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012 (pp. 121-130). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/2261250.2261269