Speaker
Description
We propose a sublinear algorithm for probabilistic testing of the discrete Fréchet distance - a standard similarity measure for curves.
We assume the algorithm is given access to the input curves via a query oracle that 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 have discrete Fréchet distance at most $\delta$
or they are ''$\varepsilon$-far'' (for $0 < \varepsilon < 2$) from being similar, i.e., an $\varepsilon$-fraction of the curves must be ignored for them to become similar.
We present an algorithm that is sublinear under two assumptions (i) that the curves are $\kappa$-straight, meaning they are $\kappa$-approximate shortest paths in the ambient metric space, for some $\kappa \ll n$, and (ii) that they have edge lengths within a constant factor of $\delta$ (we later relax this toward a weaker uniform sampling condition). The algorithm uses $O(\frac{\kappa}{\varepsilon} \log\frac{\kappa}{\varepsilon})$ queries and it is given the value of $\kappa$ in advance.
Our algorithm works in a matrix representation of the input and may be of independent interest to matrix testing.
