AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

AG Audience

English

60 Minutes

Saarbrücken

Given two planar polygonal curves, there are many ways
to define a notion of similarity between them. One popular
such measure is the Frechet distance. Since it has been
introduced in 1992, many variants and extensions have been
studied. Nonetheless, even more than 20 years later, the
original O(n^2 log n) algorithm by Alt and Godau remains
the state of the art (here n denotes the number of
vertices on each curve). We present two new algorithmic
approaches to the problem.

First, we extend an approach by Agarwal et al for the
discrete Frechet distance to the continuous case. We give
a randomized algorithm to compute the Fechet distance in
time O(n^2 sqrt{log n}(loglog n)^{3/2}) on a pointer machine
and in time O(n^2(log log n)^2) on a word RAM. Furthermore,
we show that there is an algebraic decision tree of
subquadratic depth for the decision version. This provides
evidence that the problem is not 3SUM-hard.

Second, we show a direct algorithm that avoids the detour
through the decision version that is common to the previous
approaches. This gives a quadratic time algorithm for the
Frechet distance between polygonal curves in R^d under
polyhedral distance functions (e.g., L_1 and L_infty).
For the exact Euclidean case, our framework currently
yields an algorithm with running time O(n^2 log^2 n).

Based on joint work with K. Buchin, M. Buchin, R. van
Leusden, and W. Meulemans.

--email hidden

passcode not visible

logged in users only