Constant Approximation of Fréchet Distance in Strongly Subquadratic Time

Let τ and σ be two polygonal curves in →., ^d for any fixed d. Suppose that τ and σ have n and m vertices, respectively, and m≤ n. While conditional lower bounds prevent approximating the Fréchet distance between τ and σ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of n^c in strongly subquadratic time, for some constant cϵ(0,1). We present a randomized algorithm with running time O(nm^0.99log(n/ϵ)) that approximates the Fréchet distance within a factor of 7+ϵ, with a success probability at least 1-1/n⁶. We also adapt our techniques to develop a randomized algorithm that approximates the discrete Fréchet distance within a factor of 7+ϵ in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time.