Source-linked AI summary
Computing the Discrete Fréchet Distance in Subquadratic Time
Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, Micha Sharir
TL;DR
The paper addresses the lack of subquadratic algorithms for discrete Fréchet distance on arbitrary point sequences. It uses geometric matrix compaction encoded by finite automata and achieves subquadratic running time with linear storage, while continuous Fréchet distance remains open.
Problem
No subquadratic algorithm was known for exact or approximate Fréchet distance on arbitrary curves or sequences.
Method
The algorithm uses geometric arrangement faces and finite automata to compact reachability states while processing blocks of A and subsequences of B.
Results
O(mn log log n / log n) time and O(n+m) storage compute planar discrete Fréchet distance for sequences of lengths m ≤ n.
Takeaways & Limitations
The discrete Fréchet distance admits a subquadratic algorithm for arbitrary planar point sequences rather than only restricted curve classes.
Takeaways & Limitations
The paper leaves subquadratic computation of continuous Fréchet distance as an open problem.
Abstract
from arXiv · showhide
The Fréchet distance is a similarity measure between two curves $A$ and $B$: Informally, it is the minimum length of a leash required to connect a dog, constrained to be on $A$, and its owner, constrained to be on $B$, as they walk without backtracking along their respective curves from one endpoint to the other. The advantage of this measure on other measures such as the Hausdorff distance is that it takes into account the ordering of the points along the curves. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on $n$ and $m$ specific pebbles on the curves $A$ and $B$, respectively. These frogs hop from a pebble to the next without backtracking. The discrete Fréchet distance can be computed by a rather straightforward quadratic dynamic programming algorithm. However, despite a considerable amount of work on this problem and its variations, there is no subquadratic algorithm known, even for approximation versions of the problem. In this paper we present a subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane, of respective lengths $m\le n$. The algorithm runs in $O(\dfrac{mn\log\log n}{\log n})$ time and uses $O(n+m)$ storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automata.
1 Introduction
The paper formalizes discrete Fréchet distance through ordered, non-backtracking frog movements and presents a subquadratic algorithm based on geometric compaction and finite automata. It reports extensions to higher-dimensional discrete and planar semi-continuous variants, while leaving continuous Fréchet distance open.
- Problem setting: The discrete Fréchet distance is the smallest leash length allowing two frogs to traverse point sequences in order without backtracking.Each move advances exactly one frog when both the pre- and post-jump distances are at most δ.
- Prior gap: No subquadratic algorithm was known for exact or approximate Fréchet distance on arbitrary curves or sequences.Existing subquadratic results applied only to restricted curve classes.
- Main result: O(mn log log n / log n) time and O(n+m) space compute the discrete Fréchet distance for planar sequences with m ≤ n.The decision procedure runs in O(mn log log n / log^2 n) time, and distance selection adds only an O(log n) factor.
- Scope and open problems: The technique extends within the same time bound to discrete Fréchet distance in any dimension d ≥ 3 and planar semi-continuous Fréchet distance.A comparable extension to continuous Fréchet distance was not available and remains an open problem.
- Approach: The decision procedure compacts a reachability matrix by processing selected boundary rows, blocks of A, and subsequences of B through finite automata.B is partitioned into subsequences of length Θ(log n / log log n), each processed as one symbol in constant time.
- Approach: The compaction uses the geometric arrangement of disks centered at A to create repeated arrangement faces for points of B.The automaton operates on these faces rather than directly on the input points, yielding the subquadratic performance.
2 The decision procedure
The decision procedure reduces the discrete Fréchet decision problem to reachability through structured states, processing A in layers and blocks. Its finite-state encoding yields subquadratic time with linear storage.
- Decision setup: The procedure tests whether δdF(A, B) ≤ δ by deciding reachability in the graph Gδ, after scaling δ to 1.It processes A as layers of Θ(log^2 n) points and blocks of Θ(log n) points.
- State representation: Each aggregate state (f, S_f) records the current arrangement face and the disks whose centers remain reachable by the A-frog.Valid transitions update these reachable disk sets while respecting legal interleavings of A- and B-frog moves.
- Block processing: The block automaton is built from A alone and processes B through arrangement faces, while flags identify reachable placements entering the block.This separation allows the same block-specific automaton structure to be applied to the B-sequence.
- Block processing: The automaton is represented as a Mealy machine whose transitions emit the flag strings needed to summarize intermediate states.The output associated with a transition encodes the sequence of flags produced while processing a subsequence of B.
- Complexity control: Choosing blocks of size c2 log n controls the automaton size, which is at most O(n^1/4), while constructing the transition table takes O(n log log n / log n) time.The bound uses O(m^2) arrangement faces and a pessimistic 2^m bound on feasible disk subsets.
- Overall procedure: Processing one layer costs O(n log log n), and all Θ(m / log^2 n) layers require O(mn log log n / log^2 n) time and O(n + m) space.Layer storage is released after processing, so only linear space is retained.
3 Solving the optimization problem
The optimization algorithm combines the decision procedure with binary search over critical pairwise distances to compute the discrete Fréchet distance.
- The optimization procedure binary-searches the mn pairwise distances between points of A and B, using distance selection to identify each tested critical value.Critical values are distances at which edges enter Gδ.
- O(log n) decision-procedure calls yield the paper’s main optimization result.
- Theorem 3.1 computes the discrete Fréchet distance for sequences with m ≤ n.
- The algorithm uses O(n + m) space.
4 An exponential lower bound on the number of states
The paper constructs instances with exponentially many aggregate automaton states, establishing a central bottleneck for the algorithm’s state-based compression.
- The number of aggregate states can be exponential in m in the worst case.The construction uses 2m disks arranged so that different stepping-stone sequences realize different states.
- The disk construction places even-indexed red disks near one another with a large common intersection, while each blue disk intersects one neighboring red disk but avoids the next.
- For every subset S of the final red-disk family, a corresponding sequence B_S realizes exactly the disks in S as reachable terminal states.
- The construction encodes membership in S through optional detours between arrangement faces: omitted red disks induce detours, while included disks permit direct movement and waiting.
- This lower bound makes the potentially exponential state space the major efficiency bottleneck and motivates seeking input-specific reductions.
5 Discussion and open problems
The paper concludes with a subquadratic discrete Fréchet algorithm and identifies extensions to continuous and semi-continuous variants, as well as faster running time, as open problems.
- The algorithm computes the discrete Fréchet distance between two point sequences in subquadratic time.
- Open problems include extending the approach to continuous or semi-continuous Fréchet distance and reducing the running time further.