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

Maike Buchin, Anne Driemel, Bettina Speckmann

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. The classic Fréch…