Back to Search
Start Over
Complexity and Algorithms for the Discrete Fr\'echet Distance Upper Bound with Imprecise Input
- Publication Year :
- 2015
-
Abstract
- 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.<br />Comment: 15 pages, 8 figures
- Subjects :
- Computer Science - Computational Geometry
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1509.02576
- Document Type :
- Working Paper