Point set pattern matching in 3-D

We give an algorithm for matching finite points sets in Euclidean 3-space, R(3). The algorithm runs in O(kn(5/2)[lambda(6)(n)/n](1/4) log n) time, where k is the size of the pattern and n is the size of the sample set. Further, if the pattern we seek to match is a collinear set, the running time of our algorithm reduces to O(n(2) + kn(3/2) [lambda(6)(n)/n](1/4) log n). These results improve upon the O(kn(3)) running time of the algorithm given in (De Rezende and Lee, 1995) for the case d = 3.