Speaker: Rinat Ben Avraham (TAU)

Title: Computing the Discrete Fr\'echet Distance in Subquadratic Time

Abstract:
---------

We present a subquadratic algorithm for computing the discrete
Fr\'echet distance between two sequences of points in the plane, of 
respective lengths $m$ and $n$. The algorithm runs in
$O\left(\dfrac{mn\log\log n}{\log n}\right)$ time and uses $O(n+m)$ storage.

The discrete Fr\'echet distance problem is a variant of the (more standard,
continuous) Fr\'echet distance problem. The continuous Fr\'echet distance 
is a measure which can be used to estimate the similarity between two curves. 
Informally, it is the smallest length of a leash with which a person walking 
along one curve can walk a dog along the second curve, where both person and
dog cannot backtrack along their curves.
The discrete Fr\'echet distance is a variant of this measure, that only
considers certain points (or vertices) along the two curves.

The currently best known solution for the continuous Fr\'echet distance
problem was given by Alt and Godau in 1995, and has near-quadratic 
running time (that is, $O(nm \log(nm)$ time). Until now the best known 
solution for the discrete Fr\'echet distance had $O(mn)$ running time 
(Eiter and Manila, 1994).

This is a joint work with P. K. Agarwal, H. Kaplan and M. Sharir.