Pattern Matching for Spatial Point Sets

Abstract

Two sets of points in d-dimensional space are given: a data set D consisting of N points, and a pattern set or probe P consisting of k points. We address the problem of determining whether there is a transformation, among a specified group of transformations of the space, carrying P into or near (meaning at a small directed Hausdorff distance of) D. The groups we consider are translations and rigid motions. Runtimes of approximately O(nlogn) and O(n^dlogn) respectively are obtained (letting n=max{N,k} and omitting the effects of several secondary parameters). For translations, a runtime of approximately O(n(ak+1)log^2n) is obtained for the case that a constant fraction α<1 of the points of the probe is allowed to fail to match.