Complexity and Algorithms for the Discrete Fréchet Distance Upper Bound with Imprecise Input.
2015
We study the problem of computing the upper bound of the discrete Fr\'{e}chet distance for imprecise input, and prove that the problem is NP-hard. This solves an open problem posed in 2010 by Ahn \emph{et al}. If shortcuts are allowed, we show that the upper bound of the discrete Fr\'{e}chet distance with shortcuts for imprecise input can be computed in polynomial time and we present several efficient algorithms.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
25
References
1
Citations
NaN
KQI