Data Structures for Approximate Discrete Fréchet Distance

Abstract

The Fréchet distance is a popular distance measure between curves $P$ and $Q$. Conditional lower bounds prohibit $(1+\epsilon )$-approximate Fréchet distance computations in strongly subquadratic time, even when preprocessing $P$ using any polynomial amount of time and space. As a consequence, the Fréchet distance has been studied under realistic input assumptions, for example, assuming both curves are $c$-packed. In this paper, we study $c$-packed curves in Euclidean space ${\mathbb{R}}^d$ and in general geodesic metrics $\mathcal{X}$. In ${\mathbb{R}}^d$, we provide a nearly-linear time static algorithm for computing the $(1+\epsilon )$-approximate continuous Fréchet distance between $c$-packed curves. Our algorithm has a linear dependence on the dimension $d$, as opposed to previous algorithms which have an exponential dependence on $d$. In general geodesic metric spaces $\mathcal{X}$, little was previously known. We provide the first data structure, and thereby the first algorithm, under this model. Given a $c$-packed input curve $P$ with $n$ vertices, we preprocess it in $O(n\log n)$ time, so that given a query containing a constant $\epsilon$ and a curve $Q$ with $m$ vertices, we can return a $(1+\epsilon )$-approximation of the discrete Fréchet distance between $P$ and $Q$ in time polylogarithmic in $n$ and linear in $m$, $1/\epsilon$, and the realism parameter $c$. Finally, we show several extensions to our data structure; to support dynamic extend/truncate updates on $P$, to answer map matching queries, and to answer Hausdorff distance queries.

To appear in ISAAC 2024