TY - JOUR

T1 - Computing the Fréchet distance with a retractable leash

AU - Buchin, K.A.

AU - Buchin, M.E.

AU - van Leusden, R.

AU - Meulemans, W.

AU - Mulzer, W.

PY - 2016/6/22

Y1 - 2016/6/22

N2 - All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fréchet distance between polygonal curves in Rd under polyhedral distance functions (e.g., L1 and L∞). We also get a (1+ε)-approximation of the Fréchet distance under the Euclidean metric, in quadratic time for any fixed ε>0. For the exact Euclidean case, our framework currently yields an algorithm with running time O(n2log2n). However, we conjecture that it may eventually lead to a faster exact algorithm.

AB - All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fréchet distance between polygonal curves in Rd under polyhedral distance functions (e.g., L1 and L∞). We also get a (1+ε)-approximation of the Fréchet distance under the Euclidean metric, in quadratic time for any fixed ε>0. For the exact Euclidean case, our framework currently yields an algorithm with running time O(n2log2n). However, we conjecture that it may eventually lead to a faster exact algorithm.

KW - Fréchet distanceApproximationPolyhedral distances

UR - http://link.springer.com/article/10.1007%2Fs00454-016-9800-8

U2 - 10.1007/s00454-016-9800-8

DO - 10.1007/s00454-016-9800-8

M3 - Article

SN - 0179-5376

VL - 56

SP - 315

EP - 336

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -