Static and Streaming Data Structures for Fréchet Distance Queries

Abstract

Given a curve $P$ with points in ${\mathbb{R}}^d$ in a streaming fashion, and parameters $\epsilon >0$ and $k$, we construct a distance oracle that uses $O(\frac{1}{\epsilon }{)}^{kd}\log {\epsilon }^{-1}$ space, and given a query curve $Q$ with $k$ points in ${\mathbb{R}}^d$, returns in $\tilde{O}(kd)$ time a $1+\epsilon$ 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.