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

Research output: Contribution to conferenceAbstractAcademic

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 languageEnglish
Pages43-46
Publication statusPublished - 2013
Event29th European Workshop on Computational Geometry (EuroCG 2013) - Braunschweig, Germany
Duration: 17 Mar 201320 Mar 2013
Conference number: 29

Workshop

Workshop29th European Workshop on Computational Geometry (EuroCG 2013)
Abbreviated titleEuroCG 2013
CountryGermany
CityBraunschweig
Period17/03/1320/03/13

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.