Fr\'echet Distance in Subquadratic Time

Let m and n be the numbers of vertices of two polygonal curves in Rᵈ for any fixed d such that m ≤ n. Since it was known in 1995 how to compute the Fr\'{e}chet distance of these two curves in O(mnlog (mn)) time, it has been an open problem whether the running time can be reduced to o(n²) when m = Ω(n). In the mean time, several well-known quadratic time barriers in computational geometry have been overcome: 3SUM, some 3SUM-hard problems, and the computation of some distances between two polygonal curves, including the discrete Fr\'{e}chet distance, the dynamic time warping distance, and the geometric edit distance. It is curious that the quadratic time barrier for Fr\'{e}chet distance still stands. We present an algorithm to compute the Fr\'echet distance in O(mn(loglog n)2+μlog n/log1+μ m) expected time for some constant μ ∈ (0,1). It is the first algorithm that returns the Fr\'{e}chet distance in $o(mn)$ time when m = Ω(nε) for any fixed ε ∈ (0,1].