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

Abstract

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(log log 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((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/α) log3 n) time for any α ∈ [1, n], assuming m ≤ n and constant dimension d.