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

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

doi:10.1145/2261250.2261269

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

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012
Pages	121-130
Number of pages	10
DOIs	https://doi.org/10.1145/2261250.2261269
State	Published - Jul 23 2012
Event	28th Annual Symposuim on Computational Geometry, SCG 2012 - Chapel Hill, NC, United States Duration: Jun 17 2012 → Jun 20 2012

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry

Other

Other	28th Annual Symposuim on Computational Geometry, SCG 2012
Country	United States
City	Chapel Hill, NC
Period	6/17/12 → 6/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

How to walk your dog in the mountains with no magic leash. / Har-Peled, Sariel; Nayyeri, Amir; Sidiropoulos, Anastasios; Salavatipour, Mohammad.

Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012. 2012. p. 121-130 (Proceedings of the Annual Symposium on Computational Geometry).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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. Proceedings of the Annual Symposium on Computational Geometry, pp. 121-130, 28th Annual Symposuim on Computational Geometry, SCG 2012, Chapel Hill, NC, United States, 6/17/12. https://doi.org/10.1145/2261250.2261269

@inproceedings{2cf8a293daf24b0aaf303bd70172260b,

title = "How to walk your dog in the mountains with no magic leash",

abstract = "We describe a O(log n)-approximation algorithm for computing the homotopic Frech{\'e}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{\'e}t distance, or the minimum height of a homotopy, is in NP.",

keywords = "Approximation algorithms, Frech{\'e}t distance",

author = "Sariel Har-Peled and Amir Nayyeri and Anastasios Sidiropoulos and Mohammad Salavatipour",

year = "2012",

month = jul

day = "23",

doi = "10.1145/2261250.2261269",

language = "English (US)",

isbn = "9781450312998",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "121--130",

booktitle = "Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012",

note = "28th Annual Symposuim on Computational Geometry, SCG 2012 ; Conference date: 17-06-2012 Through 20-06-2012",

}

TY - GEN

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

AU - Har-Peled, Sariel

AU - Nayyeri, Amir

AU - Sidiropoulos, Anastasios

AU - Salavatipour, Mohammad

PY - 2012/7/23

Y1 - 2012/7/23

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Frechét distance

UR - http://www.scopus.com/inward/record.url?scp=84863901950&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863901950&partnerID=8YFLogxK

U2 - 10.1145/2261250.2261269

DO - 10.1145/2261250.2261269

M3 - Conference contribution

AN - SCOPUS:84863901950

SN - 9781450312998

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 121

EP - 130

BT - Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012

T2 - 28th Annual Symposuim on Computational Geometry, SCG 2012

Y2 - 17 June 2012 through 20 June 2012

ER -

Access to Document

10.1145/2261250.2261269