Computing the Fréchet distance with shortcuts is NP-hard

M. Buchin; A. Driemel; B. Speckmann

Computing the Fréchet distance with shortcuts is NP-hard

Research output: Contribution to conference › Abstract › Academic

83 Downloads (Pure)

Abstract

We study the shortcut Fréchet distance, a natural variant of the Fréchet distance that allows us to take shortcuts from and to any point along one of the curves. We show that, surprisingly, the problem of computing the shortcut Fréchet distance exactly is NP-hard. Furthermore, we give a 3-approximation algorithm for the decision version of the problem.

Original language	English
Pages	43-46
Publication status	Published - 2013
Event	29th European Workshop on Computational Geometry (EuroCG 2013) - Braunschweig, Germany Duration: 17 Mar 2013 → 20 Mar 2013 Conference number: 29

Workshop

Workshop	29th European Workshop on Computational Geometry (EuroCG 2013)
Abbreviated title	EuroCG 2013
Country	Germany
City	Braunschweig
Period	17/03/13 → 20/03/13

Access to Document

publishers versionFinal published version, 356 KB

Fingerprint Dive into the research topics of 'Computing the Fréchet distance with shortcuts is NP-hard'. Together they form a unique fingerprint.

Cite this

Buchin, M., Driemel, A., & Speckmann, B. (2013). Computing the Fréchet distance with shortcuts is NP-hard. 43-46. Abstract from 29th European Workshop on Computational Geometry (EuroCG 2013), Braunschweig, Germany.

@conference{bdaa35b7d24f4ce0b9541a46ba3fb856,

title = "Computing the Fr{\'e}chet distance with shortcuts is NP-hard",

abstract = "We study the shortcut Fr{\'e}chet distance, a natural variant of the Fr{\'e}chet distance that allows us to take shortcuts from and to any point along one of the curves. We show that, surprisingly, the problem of computing the shortcut Fr{\'e}chet distance exactly is NP-hard. Furthermore, we give a 3-approximation algorithm for the decision version of the problem.",

author = "M. Buchin and A. Driemel and B. Speckmann",

year = "2013",

language = "English",

pages = "43--46",

note = "29th European Workshop on Computational Geometry (EuroCG 2013), EuroCG 2013 ; Conference date: 17-03-2013 Through 20-03-2013",

}

TY - CONF

T1 - Computing the Fréchet distance with shortcuts is NP-hard

AU - Buchin, M.

AU - Driemel, A.

AU - Speckmann, B.

PY - 2013

Y1 - 2013

N2 - We study the shortcut Fréchet distance, a natural variant of the Fréchet distance that allows us to take shortcuts from and to any point along one of the curves. We show that, surprisingly, the problem of computing the shortcut Fréchet distance exactly is NP-hard. Furthermore, we give a 3-approximation algorithm for the decision version of the problem.

AB - We study the shortcut Fréchet distance, a natural variant of the Fréchet distance that allows us to take shortcuts from and to any point along one of the curves. We show that, surprisingly, the problem of computing the shortcut Fréchet distance exactly is NP-hard. Furthermore, we give a 3-approximation algorithm for the decision version of the problem.

M3 - Abstract

SP - 43

EP - 46

ER -