Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 1998 | public
Book Section - Chapter

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(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.

Additional Information

© 1998 IEEE. Date of Current Version: 06 August 2002. Thanks to Amihood Amir and Piotr Indyk for helpful communications.

Additional details

August 19, 2023
October 24, 2023