2013/10/31 by Rinat Ben Avraham, Omrit Filtser, Haim Kaplan +2 · 2 citations
Computer Science · #cs.CG
published as ACM Trans. Algorithms 11(4): 29 (2015) · 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)
arxiv created 2016/09/07 · arxiv updated 2016/09/09
The Fréchet distance is a well studied similarity measures between curves. The 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 discrete Fréchet distance with shortcuts, which captures the similarity between (sampled) curves in the presence of outliers. For the two-sided case, where shortcuts are allowed in both curves, we give an O((m2/3n2/3+m+n)log3 (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+ε) expected time, for any ε>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)∈ A× B whose distance \rm 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.