Pattern Matching for Spatial Point Sets

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(n log n) and O(n d log n) respectively are obtained (letting n = maxfN; kg and omitting the effects of several secondary parameters). For translations, a runtime of approximately O(n(ak + 1) log 2 n) is obtained for the case that a constant fraction a ! 1 of the points of the probe is allowed to fail to match. 1 Introduction 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. One wishes to determine whether there is a transformation, among a specified group..