The Discrete and Semicontinuous Frechet Distance with Shortcuts via Approximate Distance Counting and Selection

摘要

The Frechet distance is a well-studied similarity measure between curves. The discrete Frechet distance is an analogous similarity measure, defined for two sequences of mand n points, where the points are usually sampled from input curves. We consider a variant, called the discrete Frechet 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+epsilon)) expected time, for any epsilon > 0. When shortcuts are allowed in both curves, we give an O((m(2/3)n(2/3) + m + n)log(3)(m + n))-time deterministic algorithm.