Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
Siu-Wing Cheng, Haoqiang Huang, Shuo Zhang · 2025
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 nc in strongly subquadratic time, for some constant cϵ(0,1). We present a randomized algorithm with running time O(nm0.99log(n/ϵ)) that approximates the Fréchet distance within a factor of 7+ϵ, with a success probability at least 1-1/n6. 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.