A Subquadratic n^ε-approximation for the Continuous Fréchet Distance
share
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 ℝ^d in O(mn (loglog n)^2) 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échet 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((n^3 / α^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^3 n) time for any α∈ [1, n], assuming m ≤ n and constant dimension d.
READ FULL TEXT