We consider the problem of computing the Fr\’echet distance between twocurves for which the exact locations of the vertices are unknown . This problem was recently shown to be NP-hard in 2D, and it is unclear how to compute an optimalvertex placement at all . We present the first general algorithmic framework for this problem . We prove that it results in a polynomial-time algorithm for curves in 1D with intervalsas uncertainty regions . In contrast, we show that the problem is NP-Hard in . In the case that vertices must be placed to maximise the . Fr\’EChet distance, we also investigate the discrete weak Fr\’echhet distance . The optimal placement of vertices in . 1D can be computed inpolynomial time. We also prove that the . problem can be . computed in Polynomial Time. In the . optimal

**Author(s) :**Kevin Buchin, Maarten Löffler, Tim Ophelders, Aleksandr Popov, Jérôme Urhausen, Kevin Verbeek

**Links :**PDF - Abstract

**Code :**

Keywords : problem - fr - distance - d - time -