The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
Rinat Ben Avraham, Omrit Filtser, Haim Y. Kaplan, Matthew J. Katz, Micha Sharir · 2014
The Fréchet distance is a well studied similarity measure between curves. The discrete Fréchet distance is an analogous similarity measure, defined for two sequences of m and n points, where the points are usually sampled from input curves. We consider a variant, called the discrete Fréchet distance with shortcuts, which captures the similarity between (sampled) curves in the presence of outliers. When shortcuts are allowed only in one noise-containing curve, we give a randomized algorithm that runs in O((m+n)6/5+ϵ) expected time, for any ϵ > 0. When shortcuts are allowed in both curves, we give an O((m2/3n2/3 + m + n) log3(m + n))-time deterministic algorithm.