We consider the problem of computing the Fr\'echet distance between two curves for which the exact locations of the vertices are unknown. Each vertex may be placed in a given uncertainty region for that vertex, and the objective is to place vertices so as to minimise the Fr\'echet distance. This problem was recently shown to be NP-hard in 2D, and it is unclear how to compute an optimal vertex 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 intervals as uncertainty regions. In contrast, we show that the problem is NP-hard in 1D in the case that vertices are placed to maximise the Fr\'echet distance. We also study the weak Fr\'echet distance between uncertain curves. While finding the optimal placement of vertices seems more difficult than the regular Fr\'echet distance -- and indeed we can easily prove that the problem is NP-hard in 2D -- the optimal placement of vertices in 1D can be computed in polynomial time. Finally, we investigate the discrete weak Fr\'echet distance, for which, somewhat surprisingly, the problem is NP-hard already in 1D.

翻译：我们考虑在两个曲线之间计算Fr\'echet距离的问题, 这两个曲线的脊椎的确切位置未知。 每个脊椎都可能位于该脊椎的不确定区域, 目标是将脊椎放置在给定的不确定区域, 以便尽可能缩小Fr\'echet距离。 这个问题最近被显示在 2D 中是 NP- 硬的, 并且目前还不清楚如何计算出最佳的脊椎位置。 我们为这一问题提供了第一个通用的算法框架。 我们证明它的结果是, 1D 曲线的多音时算法, 间隔为不确定区域。 相比之下, 我们显示问题在于1D 的NP- 硬值, 以便最大限度地缩小 Fr\'echet 距离。 我们还研究Fr\' etchet 之间最弱的Fr\ echetch 距离。 找到最佳的脊椎定位似乎比常规的Fr\'echchet距离要困难得多。 事实上, 我们很容易地可以证明, 问题在 2D 中是PP- hard 。