Property Testing of Curve Similarity

TY - GEN

T1 - Property Testing of Curve Similarity

AU - Afshani, Peyman

AU - Buchin, Maike

AU - Driemel, Anne

AU - Richter, Marena

AU - Wong, Sampson

PY - 2025/10/1

Y1 - 2025/10/1

N2 - 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 “ε-far” (for 0 < ε < 2) from being similar, i.e., more than an ε-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 ≪ n. The first algorithm uses O(εt log εt ) 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 (Equation Presented) 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 + ε′)-approximate testing using essentially the same bounds as stated above with an additional factor of poly(ε1′ ).

AB - 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 “ε-far” (for 0 < ε < 2) from being similar, i.e., more than an ε-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 ≪ n. The first algorithm uses O(εt log εt ) 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 (Equation Presented) 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 + ε′)-approximate testing using essentially the same bounds as stated above with an additional factor of poly(ε1′ ).

KW - Curve Similarity

KW - Fréchet distance

KW - Monotonicity Testing

KW - Property Testing

KW - Trajectory Analysis

UR - https://www.scopus.com/pages/publications/105019051546

U2 - 10.4230/LIPIcs.ESA.2025.84

DO - 10.4230/LIPIcs.ESA.2025.84

M3 - Article in proceedings

AN - SCOPUS:105019051546

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 33rd Annual European Symposium on Algorithms, ESA 2025

A2 - Benoit, Anne

A2 - Kaplan, Haim

A2 - Wild, Sebastian

A2 - Wild, Sebastian

A2 - Herman, Grzegorz

PB - Dagstuhl Publishing

T2 - 33rd Annual European Symposium on Algorithms, ESA 2025

Y2 - 15 September 2025 through 17 September 2025

ER -