论文标题
有效的Fréchet距离查询
Efficient Fréchet distance queries for segments
论文作者
论文摘要
我们研究了构建可以存储二维多边形曲线$ p $的数据结构的问题，以便在任何查询段$ \ overline {ab} $中，一个人可以有效地计算$ p $和$ p $和$ \ overline {ab} $之间的fréchet距离。首先，我们提出一个尺寸$ o（n \ log n）$的数据结构，该数据结构可以计算$ p $和水平查询段$ \ OVERLINE {ab} $之间的fréchet距离，其中$ o（\ log n）$ time，其中$ n $是$ p $ $ p $的$ n $。与先前的工作相比，这大大降低了所需的空间。我们扩展了允许的查询类型，因为我们允许查询是水平段$ \ operline {ab} $，以及两个点$ s，t \ in p $（不一定是顶点），并要求$ \ overline {ab} $和$ p $ in $ s $ s $ s $ s $和$ s $和$ s $和$ p $之间的fréchet距离。使用$ o（n \ log^2n）$存储，此类查询采用$ o（\ log^3 n）$时间，简化并显着改善了先前的结果。然后，我们将结果概括为查询任意取向的段。我们提供一个$ o（nk^{3+ \ varepsilon}+n^2）$大小数据结构，其中$ k \ in [1..n] $是用户可以选择的参数，而$ \ varepsilon> 0 $是任意的小常数$ \ OVERLINE {AB} $和$ s $和$ t $ o（（n/k）\ log^2n+\ log^4 n）$ p $ in $ s $ in in $ s $和$ t的曲线。这是第一个允许有效的精确Fréchet距离查询的结果。 我们还提出了数据结构的两个应用：我们表明我们可以计算$ O（N^{5/2+\ varepsilon}）$的多边形曲线的本地$Δ$简化（相对于fréchet距离）$，我们可以有效地找到一个$ \ ab的$ \ ab} $ \ ab} $ \ ab} $ \ ab}的时间{ $ p $的子库。
We study the problem of constructing a data structure that can store a two-dimensional polygonal curve $P$, such that for any query segment $\overline{ab}$ one can efficiently compute the Fréchet distance between $P$ and $\overline{ab}$. First we present a data structure of size $O(n \log n)$ that can compute the Fréchet distance between $P$ and a horizontal query segment $\overline{ab}$ in $O(\log n)$ time, where $n$ is the number of vertices of $P$. In comparison to prior work, this significantly reduces the required space. We extend the type of queries allowed, as we allow a query to be a horizontal segment $\overline{ab}$ together with two points $s, t \in P$ (not necessarily vertices), and ask for the Fréchet distance between $\overline{ab}$ and the curve of $P$ in between $s$ and $t$. Using $O(n\log^2n)$ storage, such queries take $O(\log^3 n)$ time, simplifying and significantly improving previous results. We then generalize our results to query segments of arbitrary orientation. We present an $O(nk^{3+\varepsilon}+n^2)$ size data structure, where $k \in [1..n]$ is a parameter the user can choose, and $\varepsilon > 0$ is an arbitrarily small constant, such that given any segment $\overline{ab}$ and two points $s, t \in P$ we can compute the Fréchet distance between $\overline{ab}$ and the curve of $P$ in between $s$ and $t$ in $O((n/k)\log^2n+\log^4 n)$ time. This is the first result that allows efficient exact Fréchet distance queries for arbitrarily oriented segments. We also present two applications of our data structure: we show that we can compute a local $δ$-simplification (with respect to the Fréchet distance) of a polygonal curve in $O(n^{5/2+\varepsilon})$ time, and that we can efficiently find a translation of an arbitrary query segment $\overline{ab}$ that minimizes the Fréchet distance with respect to a subcurve of $P$.
