Property Testing of Curve Similarity

Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, Sampson WongarXiv 2025 · DOI · arXiv

Abstract

Measuring the similarity between trajectories is a critical task in computational geometry, yet standard metrics like the Fréchet distance typically require quadratic time to compute. This paper introduces the first sublinear-time algorithms for property testing the Fréchet distance. By assuming curves are "well-behaved" (specifically, $t$-straight), we demonstrate that it is possible to distinguish between similar curves and those that are "$\epsilon$-far" from similar using a number of queries that is often independent of the number of vertices $n$. We provide testers for both discrete and continuous Fréchet distances, establishing a new framework for efficient trajectory analysis in massive datasets.

Introduction

The Fréchet distance is widely considered the gold-standard similarity measure for curves and trajectories, such as GPS traces or handwriting, because it accounts for the ordering and flow of points. However, for curves with $n$ vertices, the exact computation typically takes $O(n^2)$ time, which is prohibitive for large-scale data.

This research addresses the challenge by applying the framework of Property Testing. Instead of calculating the exact distance, the goal is to decide, with high probability, whether two curves have a Fréchet distance $\le \delta$ or are "$\epsilon$-far" from having that property. A pair of curves is $\epsilon$-far if one must modify more than an $\epsilon$-fraction of the vertices to make them similar.

Methodology and the Free Space Matrix

The core of the proposed algorithms lies in the relationship between geometric curve properties and the Free Space Matrix. For two curves $P$ and $Q$, the free space matrix is a grid where an entry $(i, j)$ is "0" if the distance between vertex $p_i$ and $q_j$ is at most $\delta$.

The Free Space Matrix for discrete Fréchet distance, where '0' entries indicate pairs of vertices within distance $\delta$.

Geometric Straightness and Matrix Locality

The authors introduce the concept of $t$-straightness: a curve is $t$-straight if the distance along the curve between any two points is at most $t$ times their direct Euclidean distance. The key insight is that $t$-straightness translates into structural constraints on the free space matrix. Specifically, it ensures that the "zero-entries" (valid matching points) are clustered near the diagonal, preventing the matching path from jumping wildly across the matrix. This locality allows the algorithm to use sublinear sampling to find "barriers"—regions where no points are within distance $\delta$—to reject dissimilar curves.

Visualization of two curves $P$ and $Q$ and the geometric constraints imposed by the distance parameter $\delta$.

Proposed Algorithms

The paper provides two primary query-based algorithms:

  1. Known $t$ Tester: When the straightness constant $t$ is known, the algorithm achieves a query complexity of $O(\frac{t}{\epsilon} \log \frac{t}{\epsilon})$. Remarkably, this complexity is independent of $n$.
  2. Unknown $t$ Tester: A more complex algorithm that estimates $t$ on the fly, achieving a complexity of roughly $O(\frac{t^3 + t^2 \log n}{\epsilon})$. This remains sublinear as long as $t \ll n$.

These discrete testers are further adapted to the continuous Fréchet distance by strategically subsampling the curves, yielding similar sublinear performance bounds.

Key Results and Insights

  • Independence of $n$: For well-behaved curves, the algorithm's performance does not degrade as trajectories get longer, provided their relative straightness remains constant.
  • One-Sided Error: The testers are designed to never produce false negatives; if they reject a pair, the curves are guaranteed to be dissimilar.
  • Hausdorff Distance: As a building block, the authors also provide a simple $O(1/\epsilon)$ tester for the discrete Hausdorff distance.

Conclusion and Future Work

This work provides a theoretical foundation for sublinear trajectory analysis. While the $t$-straightness assumption covers many real-world scenarios like road networks, future work is needed to address more complex models, such as $c$-packed curves, which allow for self-intersections and more erratic movement. Additionally, determining the absolute lower bounds for query complexity in this domain remains an open challenge.

Summary updated

Abstract

We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is given access to the input curves via a query oracle: a query returns the set of vertices of the curve that lie within a radius $δ$ of a specified vertex of the other curve. The goal is to use a small number of queries to determine with constant probability whether the two curves are similar (i.e., their discrete Fréchet distance is at most $δ$) or they are ''$\varepsilon$-far'' (for $0 < \varepsilon < 2$) from being similar, i.e., more than an $\varepsilon$-fraction of the two curves must be ignored for them to become similar. We present two algorithms which are sublinear assuming that the curves are $t$-approximate shortest paths in the ambient metric space, for some $t\ll n$. The first algorithm uses $O(\frac{t}{\varepsilon}\log\frac{t}{\varepsilon})$ queries and is given the value of $t$ in advance. The second algorithm does not have explicit knowledge of the value of $t$ and therefore needs to gain implicit knowledge of the straightness of the input curves through its queries. We show that the discrete Fréchet distance can still be tested using roughly $O(\frac{t^3+t^2\log n}{\varepsilon})$ queries ignoring logarithmic factors in $t$. Our algorithms work in a matrix representation of the input and may be of independent interest to matrix testing. Our algorithms use a mild uniform sampling condition that constrains the edge lengths of the curves, similar to a polynomially bounded aspect ratio. Applied to testing the continuous Fréchet distance of $t$-straight curves, our algorithms can be used for $(1+\varepsilon')$-approximate testing using essentially the same bounds as stated above with an additional factor of poly$(\frac{1}{\varepsilon'})$.
BibTeX
@misc{afshani2025property,
  author = {Peyman Afshani and Maike Buchin and Anne Driemel and Marena Richter and Sampson Wong},
  title = {{Property Testing of Curve Similarity}},
  year = {2025},
  eprint = {2502.17277},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.17277},
}
Figure