The Discrete and Semi-continuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection Techniques

Abstract

The \emph{Fréchet distance} is a well studied similarity measures between curves. The \emph{discrete Fréchet distance} is an analogous similarity measure, defined for a sequence $A$ of $m$ points and a sequence $B$ of $n$ points, where the points are usually sampled from input curves. In this paper we consider a variant, called the \emph{discrete Fréchet distance with shortcuts}, which captures the similarity between (sampled) curves in the presence of outliers. For the \emph{two-sided} case, where shortcuts are allowed in both curves, we give an $O((m^{2/3}{n}^{2/3}+m+n){\log }^3(m+n))$-time algorithm for computing this distance. When shortcuts are allowed only in one noise-containing curve, we give an even faster randomized algorithm that runs in $O((m+n{)}^{6/5+\epsilon })$ expected time, for any $\epsilon >0$. Our techniques are novel and may find further applications. One of the main new technical results is: Given two sets of points $A$ and $B$ and an interval $I$, we develop an algorithm that decides whether the number of pairs $(x,y)\in A\times B$ whose distance $\mathrm{dist}(x,y)$ is in $I$, is less than some given threshold $L$. The running time of this algorithm decreases as $L$ increases. In case there are more than $L$ pairs of points whose distance is in $I$, we can get a small sample of pairs that contains a pair at approximate median distance (i.e., we can approximately "bisect" $I$). We combine this procedure with additional ideas to search, with a small overhead, for the optimal one-sided Fréchet distance with shortcuts, using a very fast decision procedure. We also show how to apply this technique for approximating distance selection (with respect to rank), and for computing the semi-continuous Fréchet distance with one-sided shortcuts.

This version also corrects mistakes that appeared in the journal version of this paper: "The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection." ACM Trans. Algorithms 11(4): 29 (2015)

Cited by in corpus (1)

• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails