A Subquadratic n^ε-approximation for the Continuous Fréchet Distance

The Fréchet distance is a commonly used similarity measure between curves. It is known how to compute the continuous Fréchet distance between two polylines with m and n vertices in R^d in O(mn(log log n)²) time; doing so in strongly subquadratic time is a longstanding open problem. Recent conditional lower bounds suggest that it is unlikely that a strongly subquadratic algorithm exists. Moreover, it is unlikely that we can approximate the Fr ́echet distance to within a factor 3 in strongly subquadratic time, even if d = 1. The best current results establish a tradeoff between approximation quality and running time. Specifically, Colombe and Fox (SoCG, 2021) give an O(α)-approximate algorithm that runs in O((n3/α2) log n) time for any α ∈ [√n, n], assuming m = n. In this paper, we improve this result with an O(α)-approximate algorithm that runs in O((n + mn/α) log³ n) time for any α ∈ [1, n], assuming m ≤ n and
constant dimension d.