Approximately matching polygonal curves with respect to the Fréchet distance

For the task of matching with respect to the discrete Fréchet 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(m2n2) for matching under the discrete Fréchet 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.