Efficient Fréchet distance queries for segments

Abstract

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 }^{2}n)$ 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(n{k}^{3+\epsilon }+n^2)$ size data structure, where $k\in [\mathrm{1..}n]$ is a parameter the user can choose, and $\epsilon >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 }^{2}n+{\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 $\delta$-simplification (with respect to the Fréchet distance) of a polygonal curve in $O(n^{5/2+\epsilon })$ 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$.