论文标题
近似（连续的）fréchet距离
Approximating the (Continuous) Fréchet Distance
论文作者
论文摘要
我们描述了第一个强次次级时间算法，具有次指数近似值率，用于计算两个多边形链之间的Fréchet距离。具体来说，让$ p $和$ q $为两个多边形链，$ n $顶点在$ d $ d $维欧几里得空间中，让$α\在[\ sqrt {n}，n] $中。我们的算法确定性地发现了一个$ o（α）$ - 近似时间$ o（（（n^3 /α^2）\ log n）$。特别是，我们在接近线性$ O（n \ log n）$ time中获得$ O（n）$ - 近似值，比以前最佳的结果进行了巨大改进，线性时间$ 2^{o（n）} $ - 近似值。作为我们算法的一部分，我们还描述了如何将Fréchet距离的任何近似决策程序转变为近似优化算法，该算法的近似值与任意小的恒定因子相同。将近似优化算法转换为决策过程的运行时间仅增加了$ O（\ log n）$。
We describe the first strongly subquadratic time algorithm with subexponential approximation ratio for approximately computing the Fréchet distance between two polygonal chains. Specifically, let $P$ and $Q$ be two polygonal chains with $n$ vertices in $d$-dimensional Euclidean space, and let $α\in [\sqrt{n}, n]$. Our algorithm deterministically finds an $O(α)$-approximate Fréchet correspondence in time $O((n^3 / α^2) \log n)$. In particular, we get an $O(n)$-approximation in near-linear $O(n \log n)$ time, a vast improvement over the previously best know result, a linear time $2^{O(n)}$-approximation. As part of our algorithm, we also describe how to turn any approximate decision procedure for the Fréchet distance into an approximate optimization algorithm whose approximation ratio is the same up to arbitrarily small constant factors. The transformation into an approximate optimization algorithm increases the running time of the decision procedure by only an $O(\log n)$ factor.
