The discrete Fréchet distance is a popular measure for comparing polygonal curves, often described as the minimum leash length required for a person walking along one curve to walk a dog along the other. An important variant is the discrete Fréchet distance under translation, which enables the detection of similar movement patterns regardless of their absolute spatial coordinates—a crucial task in fields like signature verification and trajectory clustering.
The Challenge of Translation Invariance
While the standard discrete Fréchet distance can be computed in $O(n^2)$ time, the translation-invariant version is significantly more computationally demanding. The previous state-of-the-art algorithm required $\tilde{O}(n^5)$ time. This approach works by constructing a geometric arrangement of $O(n^4)$ disks, where each disk represents a critical translation value. The problem then reduces to traversing the faces of this arrangement while maintaining reachability in a directed grid graph of size $N = O(n^2)$.
Algorithmic Improvements: Offline Dynamic Grid Reachability
The authors identify a key optimization in the reachability subroutine. Previous methods used a fully dynamic grid reachability algorithm, which is limited by a $\tilde{O}(\sqrt{N})$ update time. However, the sequence of updates in the Fréchet problem—determined by the traversal of the disk arrangement—is known in advance.
By recognizing this as an Offline Dynamic Grid Reachability problem, the authors bypass the bottlenecks of fully dynamic algorithms. They develop a new data structure that processes updates in batches ("chunks") and uses a succinct labeling scheme to characterize reachability between grid block boundaries and internal "terminal" nodes. This reduces the amortized update time to $\tilde{O}(N^{1/3})$, leading to an overall improved running time of $\tilde{O}(n^{4.66...})$ for the discrete Fréchet distance under translation.
Conditional Hardness and the $n^4$ Barrier
A major contribution of this work is providing evidence that the massive $O(n^4)$ overhead inherent in current algorithms is likely unavoidable. Using a reduction from the 4-Orthogonal Vectors (4-OV) problem, the authors prove a conditional lower bound of $n^{4-o(1)}$ on the running time, assuming the Strong Exponential Time Hypothesis (SETH).
This lower bound is significant because it suggests that constructing the $O(n^4)$ size arrangement—which might intuitively feel like a brute-force step—is actually fundamentally necessary in the worst case. The reduction involves intricate geometric "gadgets" that translate logical boolean constraints into the geometric constraints of curve traversals.
Key Results and Future Directions
The paper successfully narrows the complexity gap for the discrete Fréchet distance under translation:
- Improved Upper Bound: The running time is reduced from $\tilde{O}(n^5)$ to $\tilde{O}(n^{14/3}) \approx \tilde{O}(n^{4.66...})$.
- Hardness Proof: Established a conditional lower bound of $n^{4-o(1)}$ based on SETH.
- Subroutine Speedup: Solved Offline Dynamic Grid Reachability in $\tilde{O}(n^{2/3})$ amortized time per update.
Despite these advances, a gap remains between the $n^4$ lower bound and the $n^{4.66...}$ upper bound. Reaching $n^4$ might require an offline dynamic grid reachability solution with polylogarithmic amortized update time. Additionally, generalizing these results to higher dimensions or other transformations like rotation and scaling remains an open challenge.
Summary updated