论文标题
近似离散的Fréchet距离的数据结构
Data Structures for Approximate Discrete Fréchet Distance
论文作者
论文摘要
Fréchet距离是曲线$ P $和$ Q $之间的流行距离度量。有条件的下限禁止$（1 + \ varepsilon）$ - 近似限定时间的近似fréchet距离计算，即使使用任何多项式的时间和空间，即使在预处理$ p $的情况下进行预处理$ p $。结果，例如，假设这两种曲线都是$ c $包装的，则已经在现实的输入假设下研究了Fréchet距离。 在本文中，我们研究了欧几里得空间中的$ c $包装曲线$ \ mathbb r^d $，总的来说，Geodesic Metrics $ \ Mathcal x $。在$ \ mathbb r^d $中，我们提供了一种接近线性的时间静态算法，用于计算$（1+ \ varepsilon）$ - 近似$ C $包装曲线之间的连续fréchet距离。我们的算法对尺寸$ d $具有线性依赖，而不是先前对$ d $的指数依赖性的算法。 总的来说，总测量公制空间$ \ MATHCAL X $，以前鲜为人知。我们提供了第一个数据结构，因此在此模型下提供了第一个算法。给定$ c $包装的输入曲线$ p $带有$ n $顶点，我们以$ o（n \ log n）$时间进行预处理，以便给定包含常数$ \ varepsilon $的查询和curve $ q $ with $ m $ pertices，我们可以返回$（1+\ varepsilon $ - $ \ varepsilon $ - $ frue ffrue que frue que， $ n $的polygarithmic，$ m $，$ 1/\ varepsilon $和现实主义参数$ c $。最后，我们向数据结构展示了几个扩展。为了支持$ P $上的动态扩展/截断更新，以回答匹配查询的地图，并回答Hausdorff距离查询。
The Fréchet distance is a popular distance measure between curves $P$ and $Q$. Conditional lower bounds prohibit $(1 + \varepsilon)$-approximate Fréchet distance computations in strongly subquadratic time, even when preprocessing $P$ using any polynomial amount of time and space. As a consequence, the Fréchet distance has been studied under realistic input assumptions, for example, assuming both curves are $c$-packed. In this paper, we study $c$-packed curves in Euclidean space $\mathbb R^d$ and in general geodesic metrics $\mathcal X$. In $\mathbb R^d$, we provide a nearly-linear time static algorithm for computing the $(1+\varepsilon)$-approximate continuous Fréchet distance between $c$-packed curves. Our algorithm has a linear dependence on the dimension $d$, as opposed to previous algorithms which have an exponential dependence on $d$. In general geodesic metric spaces $\mathcal X$, little was previously known. We provide the first data structure, and thereby the first algorithm, under this model. Given a $c$-packed input curve $P$ with $n$ vertices, we preprocess it in $O(n \log n)$ time, so that given a query containing a constant $\varepsilon$ and a curve $Q$ with $m$ vertices, we can return a $(1+\varepsilon)$-approximation of the discrete Fréchet distance between $P$ and $Q$ in time polylogarithmic in $n$ and linear in $m$, $1/\varepsilon$, and the realism parameter $c$. Finally, we show several extensions to our data structure; to support dynamic extend/truncate updates on $P$, to answer map matching queries, and to answer Hausdorff distance queries.
