论文标题
Fréchet距离查询的静态和流数据结构
Static and Streaming Data Structures for Fréchet Distance Queries
论文作者
论文摘要
给定曲线$ p $带有$ \ mathbb {r}^d $的点，并以流方式和参数为$ \ varepsilon> 0 $和$ k $，我们构造了一个距离甲骨文，使用$ o（\ frac {1}} {1} {\ varepsilon} {\ varepsilon}） $ q $带有$ k $点的$ \ mathbb {r}^d $，返回$ \ tilde {o}（kd）$ time a $ 1+\ varepsilon $ y近似$ q $和$ p $之间的离散fréchet距离的近似值。 此外，我们在流模型中构建简化，将距离查询到子曲线的距离查询（在静态设置中），并引入缩放问题。我们的算法在任何维度$ d $中都起作用，因此我们在离散的Fréchet距离下概括了一些有用的工具和算法，以在高维度上有效地工作。
Given a curve $P$ with points in $\mathbb{R}^d$ in a streaming fashion, and parameters $\varepsilon>0$ and $k$, we construct a distance oracle that uses $O(\frac{1}{\varepsilon})^{kd}\log\varepsilon^{-1}$ space, and given a query curve $Q$ with $k$ points in $\mathbb{R}^d$, returns in $\tilde{O}(kd)$ time a $1+\varepsilon$ approximation of the discrete Fréchet distance between $Q$ and $P$. In addition, we construct simplifications in the streaming model, oracle for distance queries to a sub-curve (in the static setting), and introduce the zoom-in problem. Our algorithms work in any dimension $d$, and therefore we generalize some useful tools and algorithms for curves under the discrete Fréchet distance to work efficiently in high dimensions.
