Source-linked AI summary
Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
Karl Bringmann
TL;DR
The paper asks whether the Fréchet distance can be computed substantially faster than quadratic time despite limited known lower bounds. It reduces CNF-SAT to Fréchet distance computation and proves conditional hardness for exact and approximate variants, including imbalanced and c-packed curves.
Problem
Whether the Fréchet distance admits a strongly subquadratic algorithm remained open despite known mildly subquadratic algorithms and limited lower bounds.
Method
The paper reduces CNF-SAT to Fréchet distance by encoding partial assignments with clause and assignment gadgets connected by an OR-gadget.
Results
There is no O(n^{2−δ}) algorithm for continuous or discrete Fréchet distance for any δ > 0, unless SETH′ fails.
Takeaways & Limitations
The result provides strong evidence that strongly subquadratic algorithms for the Fréchet distance are unlikely under SETH′.
Takeaways & Limitations
The approximation result leaves open whether a strongly subquadratic O(1)-approximation exists, and the constant 1.001 was not optimized.
Abstract
from arXiv · showhide
The Frechet distance is a well-studied and very popular measure of similarity of two curves. Many variants and extensions have been studied since Alt and Godau introduced this measure to computational geometry in 1991. Their original algorithm to compute the Frechet distance of two polygonal curves with n vertices has a runtime of O(n^2 log n). More than 20 years later, the state of the art algorithms for most variants still take time more than O(n^2 / log n), but no matching lower bounds are known, not even under reasonable complexity theoretic assumptions. To obtain a conditional lower bound, in this paper we assume the Strong Exponential Time Hypothesis or, more precisely, that there is no O*((2-delta)^N) algorithm for CNF-SAT for any delta > 0. Under this assumption we show that the Frechet distance cannot be computed in strongly subquadratic time, i.e., in time O(n^{2-delta}) for any delta > 0. This means that finding faster algorithms for the Frechet distance is as hard as finding faster CNF-SAT algorithms, and the existence of a strongly subquadratic algorithm can be considered unlikely. Our result holds for both the continuous and the discrete Frechet distance. We extend the main result in various directions. Based on the same assumption we (1) show non-existence of a strongly subquadratic 1.001-approximation, (2) present tight lower bounds in case the numbers of vertices of the two curves are imbalanced, and (3) examine realistic input assumptions (c-packed curves).
1 Introduction
The paper addresses the open question of whether the Fréchet distance admits strongly subquadratic algorithms by relating it to SETH′. It proves conditional lower bounds for exact computation and approximation, including imbalanced and c-packed curves.
- Motivation: The Fréchet distance measures curve similarity while preserving the order of points along each curve.This distinguishes it from measures such as Hausdorff distance and motivates its use for perceptual curve similarity.
- Motivation: The existence of a strongly subquadratic algorithm for the Fréchet distance remained open despite progress toward mildly subquadratic algorithms.Strongly subquadratic means O(n^{2−δ}) time for any δ > 0.
- Main result: There is no O(n^{2−δ}) algorithm for continuous or discrete Fréchet distance for any δ > 0, unless SETH′ fails.The main theorem relates the Fréchet distance to SETH′ through a reduction from CNF-SAT.
- Extensions: There is no 1.001-approximation in strongly subquadratic time unless SETH′ fails, and whether a strongly subquadratic O(1)-approximation exists remains open.The constant 1.001 was not optimized; the result indicates that this approximation requires the same asymptotic time as exact computation up to no(1)-factors.
- Extensions: The lower bounds extend to imbalanced curves and c-packed curves, including O((nm)^{1−δ}) and O((cn)^{1−δ}) barriers for 1.001-approximation.The imbalanced result holds for any polynomial restriction of 1 ⩽ m ⩽ n, while the c-packed result holds for any polynomial restriction of 1 ⩽ c ⩽ n.
2 Preliminaries
This section defines polygonal curves, continuous and discrete Fréchet distance, CNF-SAT terminology, and the SETH′ assumption used for conditional lower bounds.
- Curve definitions: A polygonal curve is represented as a continuous piecewise-linear function through its ordered vertices, and curves can be concatenated.The notation |P| denotes the number of vertices.
- Fréchet variants: The continuous Fréchet distance is based on non-decreasing continuous traversals whose width is the maximum Euclidean distance between matched curve positions.The distance measures the narrowest leash allowing both curves to be traversed without backtracking.
- Fréchet variants: The discrete Fréchet distance uses non-decreasing staircase traversals, where each step advances one or both curves to the next vertex or leaves a vertex unchanged.This yields the frog-jumping interpretation and changes only at finitely many time steps.
- Fréchet variants: For any two curves, the continuous Fréchet distance is at most the discrete Fréchet distance.The paper states dF(P1, P2) ⩽ ddF(P1, P2).
- Realistic input curves: A c-packed curve has at most cr total curve length inside every ball of radius r, a model motivated by practical curve classes.Examples include convex-polygon boundaries, γ-fat shapes, and bounded-degree algebraic curves.
- Satisfiability assumptions: SETH′ asserts that CNF-SAT has no O*((2 − δ)^N) algorithm for any δ > 0, and the paper assumes it for all stated lower bounds.A restricted-clause version follows unless SETH′ fails, using exhaustive search when the clause count is large.
3 General curves
The paper reduces CNF-SAT to Fréchet distance using assignment and clause gadgets, proving conditional hardness for both variants and for imbalanced curve sizes.
- 3.1 The basic reduction, discrete case: The reduction splits CNF-SAT variables into two sets and constructs one curve whose assignment gadgets encode partial assignments from each set.Each assignment gadget contains clause gadgets corresponding to the formula’s clauses.
- 3.1 The basic reduction, discrete case: The constructed curves satisfy ddF(P1, P2) ⩽ 1 if and only if the CNF-SAT formula is satisfiable.The OR-gadget forces a traversal to select a pair of assignment gadgets, while one satisfying pair suffices.
- 3.1 The basic reduction, discrete case: Clause-gadget distances distinguish satisfying from non-satisfying combinations: compatible pairs are at distance at most 1, otherwise at least 1 + 2ε.This holds when the clause-gadget indices have matching parity.
- 3.1 The basic reduction, discrete case: For a satisfying assignment pair, the corresponding assignment gadgets admit a traversal of width 1; for a non-satisfying pair, every extended traversal has width greater than 1 + ε.The discrete gap is established by forcing the traversal through corresponding clause gadgets.
- 3.1 The basic reduction, discrete case: The reduction creates curves of size n = O(M · 2^(N/2)) and construction time O(NM2^(N/2)), yielding the main conditional quadratic lower bound.A strongly subquadratic or 1.001-approximate algorithm would contradict SETH′.
- 3.2 Continuous case: The same construction extends to continuous Fréchet distance: satisfiable instances have distance at most 1, while distance at most 1.001 implies satisfiability.The continuous proof controls traversal positions near clause gadgets.
- 3.3 Generalization to imbalanced numbers of vertices: For imbalanced curves, the paper rules out O((nm)^(1−δ)) algorithms whenever n^(γ−δ) ⩽ m ⩽ n^(γ+δ), for δ ⩽ γ ⩽ 1 − δ.The construction also transfers the 1.001-approximation lower bound to these size regimes.
4 Realistic inputs: c-packed curves
The paper adapts its conditional lower-bound framework to c-packed curves, ruling out strongly sublinear-in-cn 1.001-approximations under SETH′. The construction preserves satisfiability distinctions while controlling curve packing and extends the dependence-on-ε lower bound to dimensions d ≥ 5.
- 4 Realistic inputs: c-packed curves: Highly packed assignment-gadget constructions are replaced to obtain c-packed instances without losing the satisfiability encoding.The original curves are not o(n)-packed, motivating a new construction with controlled packing.
- 4 Realistic inputs: c-packed curves: 1.001-approximations with runtime O((cn)^{1−δ}) are ruled out for continuous and discrete Fréchet distance on c-packed curves, for any δ > 0, unless SETH′ fails.The result holds under any polynomial restriction of 1 ≤ c ≤ n.
- 4 Realistic inputs: c-packed curves: The OR-gadget combines assignment gadgets so a width-1 traversal exists when a satisfying assignment is present, while unsatisfiable formulas cannot traverse the extra U-shape.The construction stitches neighboring U-shapes and uses the imbalance between the two curves to force the satisfiability distinction.
- 4 Realistic inputs: c-packed curves: The constructed curves have c = Θ(M · 2^(N/2)/ℓ) and n = Θ(ℓ²M · 2^(N/2)/ℓ), enabling the polynomial-restriction lower bound.These parameter relations are used to derive the claimed dependence on c and n.
- 4 Realistic inputs: c-packed curves: In dimensions d ≥ 5, no (1 + ε)-approximation runs in O((cn/√ε)^{1−δ}) time for sufficiently small ε > 0 unless SETH′ fails.This matches the fastest known algorithm’s dependence on ε up to a polynomial.
5 Conclusion
The paper concludes that continuous and discrete Fréchet distance likely have no strongly subquadratic algorithms under SETH′. It also extends the lower bounds to approximation, imbalanced curves, and c-packed curves, while leaving several algorithmic questions open.
- 5 Conclusion: The results provide strong evidence that continuous and discrete Fréchet distance have no strongly subquadratic algorithms.
- 5 Conclusion: The extensions cover approximation algorithms and realistic c-packed input curves.
- 5 Conclusion: Open questions ask whether strongly subquadratic constant-factor approximations exist for general curves.
- 5 Conclusion: Open questions also concern near-linear-time approximation or exact algorithms for c-packed curves in dimensions 2, 3, and 4.
- 5 Conclusion: For dimensions d ≥ 5, the paper asks whether a (1 + ε)-approximation can achieve runtime ˜O(cn/√ε) on c-packed curves.