Property Testing of Curve Similarity

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 $\delta$ 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 $\delta$) 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(t\varepsilon \log 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(t3+t2\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(1$\varepsilon$′).