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.
|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||29th European Workshop on Computational Geometry (EuroCG 2013)|
|Abbreviated title||EuroCG 2013|
|Period||17/03/13 → 20/03/13|
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.