M. Clausen, A. Mosig,
Approximately
Matching Polygonal Curves with Respect to the Frechet Distance,
19th Europ. Worksh. Comp. Geom., Bonn, Germany, 2003.
Let P:[0,m]->R^2$ and
Q:[0,n]->R^2$ be polygonal curves in the plane,
G a subgroup of the affine group AGL(2,R), and
$\eps$>=0. By definition, a transformation g in G
yields a (G,$\eps$)-Frechet-match of P and Q if
the Frechet-distance of P and the transformed version
gQ of Q is at most $\eps$. In this paper we design a
c-approximation algorithm, c > 2, that constructs such
(G,c$\eps$)-Frechet-matches for both the group $G_r$
of rigid motions and the group $G_s$ generated by translations and
uniform scalings. We associate to P,Q and $\eps$ a certain
acyclic digraph $M_{m,n}$, whose edges are either weighted by closed
intervals in R ($G=G_s$) or by circular arcs ($G=G_r$). All
maximal paths in $M_{m,n}$ correspond to discrete
reparametrization pairs; such a pair yields a c-approximate
solution if the intervals assigned to the edges along the path have
a non-empty intersection. To decide whether such a path exists, we
use a dynamic programming approach, whose time complexity is
O(m^2n^2). There is related work dealing with smaller subgroups of
AGL(2,R): Alt and Godau investigated the case $G=\{1\}$, whereas
both Alt, Knauer and Wenk and Efrat, Indyk and Venkatasubramanian
studied the case $G=T_2$, which denotes the group of translations.