Data Structures for Approximate Fréchet Distance for Realistic Curves

The Fréchet distance is a popular distance measure between curves P and Q. Conditional lower bounds prohibit (1 + ε)-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 R^d and in general geodesic metrics X. In R^d, we provide a nearly-linear time static algorithm for computing the (1 + ε)-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 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(nlog n) time, so that given a query containing a constant ε and a curve Q with m vertices, we can return a (1 + ε)-approximation of the discrete Fréchet distance between P and Q in time polylogarithmic in n and linear in m, 1/ε, 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.