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 |