论文标题
连续的fréchet距离的次级$ n^ε$ -Approximation
A Subquadratic $n^ε$-approximation for the Continuous Fréchet Distance
论文作者
论文摘要
Fréchet距离是曲线之间常用的相似性度量。众所周知，如何计算两个polylines之间的连续fréchet距离，其中$ m $和$ n $ vertices in $ \ mathbb {r}^d $ in $ o（mn（mn（\ log \ log \ log n）^2）$ time;在强烈的次级时间里这样做是一个长期的开放问题。最近的条件下限表明，强大的下级算法不可能存在。此外，即使$ d = 1 $，我们不可能将fréchet距离近似于$ 3 $的$ 3 $。当前最佳结果在近似质量和运行时间之间建立了权衡。具体来说，Colombe和Fox（SocG，2021）给出了$ O（α）$ - 近似算法，该算法以$ o（（（n^3 /α^2）\ log n）$ n）$ n）$ in [\ sqrt {n}，n] $的任何$α\，假设$ m = n $。在本文中，我们使用$ O（α）$ - 近似算法改善了该结果，该算法以$ o（（（n + mn /α）\ log^3 n）$ n）$ time in [1，n] $中的任何$α\，假设$ m \ m \ leq n $和常数dimension $ d $ d $。
The Fréchet distance is a commonly used similarity measure between curves. It is known how to compute the continuous Fréchet distance between two polylines with $m$ and $n$ vertices in $\mathbb{R}^d$ in $O(mn (\log \log n)^2)$ time; doing so in strongly subquadratic time is a longstanding open problem. Recent conditional lower bounds suggest that it is unlikely that a strongly subquadratic algorithm exists. Moreover, it is unlikely that we can approximate the Fréchet distance to within a factor $3$ in strongly subquadratic time, even if $d=1$. The best current results establish a tradeoff between approximation quality and running time. Specifically, Colombe and Fox (SoCG, 2021) give an $O(α)$-approximate algorithm that runs in $O((n^3 / α^2) \log n)$ time for any $α\in [\sqrt{n}, n]$, assuming $m = n$. In this paper, we improve this result with an $O(α)$-approximate algorithm that runs in $O((n + mn / α) \log^3 n)$ time for any $α\in [1, n]$, assuming $m \leq n$ and constant dimension $d$.
