Fast constant factor approximation of curve similarity in near linear time
Constant Approximation of Fréchet Distance in Near-Linear Time
Computational Geometry
Summary
Measuring how similar two curves are can be done using something called the Fréchet distance, which is often slow to compute exactly. The authors have created an algorithm that quickly finds an answer close to the true similarity within a constant factor. Their method works for curves in any fixed number of dimensions and improves on prior algorithms, running nearly as fast as just reading the input. It also provides a way to explain the similarity it finds.
What this means in practice
- •For gis software developers: Speed up map-matching and shape comparison tasks by quickly approximating similarity between geographic curves with guaranteed error bounds.
- •For robotics engineers: Compute approximate path similarity rapidly for obstacle avoidance and trajectory planning in robots moving through complex environments.
Authors
Haoqiang Huang, Zihe Wang, Shuo Zhang
Abstract
We present a deterministic algorithm that approximates the Fréchet distance between two polygonal curves in $\mathbb{R}^d$ with $n$ and $m$ vertices within a constant factor in $O((m+n)^{1+\varepsilon})$ time, for every fixed $\varepsilon>0$ and fixed dimension $d$. The approximation factor depends only on $\varepsilon$ and $d$. No assumption on the input curves is needed, and the algorithm also reports a matching certifying the approximation. The same result holds for the discrete Fréchet distance. Our result extends the line of work initiated by Cheng, Huang, and Zhang (2025), who gave the first constant-factor approximation in strongly subquadratic time, to near-linear time. For two $n$-vertex curves, the best previous running time was $\widetilde{O}(n^{5/3})$, due to van der Horst and Ophelders (2026). Our algorithm bootstraps between two primitives: a data structure that preprocesses a single curve for comparing any two of its subcurves, and a query procedure that compares subcurves of two different curves. Given the data structure for one curve, we compare it with another curve using a surrogate assembled from subcurves of the former. The surrogate is shared by all possible starting points of a matching. Conversely, faster queries make the next data structure cheaper to build. After a number of rounds that depends only on $\varepsilon$, both preprocessing and query time are $O((m+n)^{1+\varepsilon})$. To make each round's output reusable by the next, we compactly summarize how matchings can enter and leave a pair of subcurves. These summaries can be applied to different starting points and retain the information needed to report the matchings.