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\'echet 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\'echet distance to work efficiently in high dimensions.
Categories: cs.CG cs.DS