Pattern Matching for Spatial Point Sets, David E. Cardoze and Leonard J. Schulman. Proceedings of FOCS'98.

Two sets of points in $d$-dimensional space are given: a {\it data set\/} $\D$ consisting of $N$ points, and a {\it pattern set\/} or {\it 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=\max\{N,k\}$ 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.