Complexity and Algorithms for the Discrete Fréchet Distance Upper Bound with Imprecise Input

Chenglin Fan, Binhai Zhu

We study the problem of computing the upper bound of the discrete Fréchet distance for imprecise input, and prove that the problem is NP-hard. This solves an open problem posed in…