论文标题
计算$ k $ -shortcutfréchet距离
On Computing the $k$-Shortcut Fréchet Distance
论文作者
论文摘要
Fréchet距离是多边形曲线差异的流行度量。它被定义为一种最小的公式，该公式考虑了两条曲线的所有方向延伸连续两种连续两种。由于其对噪声的敏感性，Driemel和Har-Peled在2012年引入了快捷方式Fréchet距离，在该距离上，人们可以沿其中一条曲线进行快捷方式，类似于序列的编辑距离。我们分析了此问题的参数化版本，其中快捷方式的数量由参数$ k $界定。相应的决策问题可以如下说明：给定两条多边形曲线$ t $ t $和$ b $，最多$ n $ vertices，一个参数$ k $和一个距离阈值$δ$，是否可以沿$ b $引入$ k $ k $ k $ b $，以便最终的curve curve $ $ t $ the curve $ t $ the curve $ t $ the curve $ the at the Curve $ t.我们研究了平面中多边形曲线的问题。我们为此问题提供了以下结果的复杂性分析：（i）假设指数时间 - 假设（ETH），没有算法的运行时间为$ n^{o（k）} $； （ii）在$ o（kn^{2k+2} \ log n）$中存在一种决策算法。相比之下，我们还表明，即使$ k $很大，也可以表明有效的近似决定算法也是可能的。我们提供$（3+ \ varepsilon）$ - 近似$ o（k n^2 \ log^2 n）$的近似决定算法，用于固定$ \ varepsilon $。此外，我们可以证明，如果$ k $是一个常数，并且这两条曲线是$ c $的，则包装了一些常数$ c $，则大约决定算法在接近线性的时间内运行。
The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min-max formulation that considers all direction-preserving continuous bijections of the two curves. Because of its susceptibility to noise, Driemel and Har-Peled introduced the shortcut Fréchet distance in 2012, where one is allowed to take shortcuts along one of the curves, similar to the edit distance for sequences. We analyse the parameterized version of this problem, where the number of shortcuts is bounded by a parameter $k$. The corresponding decision problem can be stated as follows: Given two polygonal curves $T$ and $B$ of at most $n$ vertices, a parameter $k$ and a distance threshold $δ$, is it possible to introduce $k$ shortcuts along $B$ such that the Fréchet distance of the resulting curve and the curve $T$ is at most $δ$? We study this problem for polygonal curves in the plane. We provide a complexity analysis for this problem with the following results: (i) assuming the exponential-time-hypothesis (ETH), there exists no algorithm with running time bounded by $n^{o(k)}$; (ii) there exists a decision algorithm with running time in $O(kn^{2k+2}\log n)$. In contrast, we also show that efficient approximate decider algorithms are possible, even when $k$ is large. We present a $(3+\varepsilon)$-approximate decider algorithm with running time in $O(k n^2 \log^2 n)$ for fixed $\varepsilon$. In addition, we can show that, if $k$ is a constant and the two curves are $c$-packed for some constant $c$, then the approximate decider algorithm runs in near-linear time.
