M. Clausen, A. Mosig, Approximately Matching Polygonal Curves
with Respect to the Frechet Distance,
Accepted for Special
Issue on the 19th Europ. Workshop on Comp. Geom. of
Computational Geometry: Theory and Applications., 2004.
In this paper we present approximate algorithms for matching two
polygonal curves with respect to the Frechet distance. We define a
discrete version of the Frechet distance as a distance measure
between polygonal curves and show that this discrete version is
bounded by the continuous version of the Frechet distance.
For the task of matching with respect to the discrete Frechet
distance, we develop an algorithm that is based on intersecting
certain subsets of the transformation group under consideration.
Our algorithm for matching two point sequences of lengths $m$ and
$n$ under the group of rigid motions has a time complexity of
O(m^2n^2) for matching under the discrete Frechet distance and can
be modified for matching subcurves, closed curves and finding
longest common subcurves. Group theoretical considerations allow us
to eliminate translation components of affine transformations and
to consider matching under arbitrary linear algebraic groups.