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/sup d/logn) 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/sup 2/n) is obtained for the case that a constant fraction /spl alpha/<1 of the points of the probe is allowed to fail to match.

Authors

• David E. Cardoze
• Leonard J. Schulman

Keywords

• Pattern matching
• Probes
• Space technology
• Runtime
• Constellation diagram
• Educational institutions
• Electronic switching systems
• Electrical capacitance tomography
• Rigid Transformation
• Secondary Parameters
• Hausdorff Distance
• Group Of Transformations
• Point Probe
• Discretion
• Convolution
• High-dimensional
• Running Time
• Fast Fourier Transform
• Paired Data
• Exact Match
• Dot Product
• Size Of Space
• Dimensional Problems
• Pullback
• Precision Parameter
• Version Of Problem
• One-dimensional Problem
• Spatial Problem
• Night Sky
• Minkowski Sum
• Binary Search
• Matching Problem
• Polylogarithmic
• Word Length
• Reduction Of Space