Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability

Karl Bringmann, Marvin Künnemann, André Nusser

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)$.

Relationship between input curves, the free-space diagram, and the resulting grid graph used for reachability analysis.

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.

An arrangement of disks representing critical translations. The algorithm traverses the faces of such an arrangement to update reachability.

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

Abstract

The discrete Fr\'echet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fr\'echet distance under translation, which enables detection of similar movement patterns in different spatial domains. For polygonal curves of length $n$ in the plane, the fastest known algorithm runs in time $\tilde{\cal O}(n^{5})$ [Ben Avraham, Kaplan, Sharir '15]. This is achieved by constructing an arrangement of disks of size ${\cal O}(n^{4})$, and then traversing its faces while updating reachability in a directed grid graph of size $N := {\cal O}(n^2)$, which can be done in time $\tilde{\cal O}(\sqrt{N})$ per update [Diks, Sankowski '07]. The contribution of this paper is two-fold. First, although it is an open problem to solve dynamic reachability in directed grid graphs faster than $\tilde{\cal O}(\sqrt{N})$, we improve this part of the algorithm: We observe that an offline variant of dynamic $s$-$t$-reachability in directed grid graphs suffices, and we solve this variant in amortized time $\tilde{\cal O}(N^{1/3})$ per update, resulting in an improved running time of $\tilde{\cal O}(n^{4.66...})$ for the discrete Fr\'echet distance under translation. Second, we provide evidence that constructing the arrangement of size ${\cal O}(n^{4})$ is necessary in the worst case, by proving a conditional lower bound of $n^{4 - o(1)}$ on the running time for the discrete Fr\'echet distance under translation, assuming the Strong Exponential Time Hypothesis.
BibTeX
@inproceedings{bringmann2019frechet,
  author = {Karl Bringmann and Marvin Künnemann and André Nusser},
  title = {{Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability}},
  booktitle = {SODA},
  year = {2019},
  doi = {10.1137/1.9781611975482.180},
}
Figure