Even faster point set pattern matching in 3D
Laurence Boxer · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1999
Several recent papers have produced successively faster running times for solution of the Point Set Matching Problem (PSPM) (finding all congruent copies of a pattern in a sample set) in Euclidean 3-space, R3. Here, we obtain further improvement in the speed with which this problem can be solved. The source of the improvement over the previous fastest running time is a better upper bound for the volume of output, derived from a recent result. The previous best sequential running time for PSPM in R3 is O{kn2[(lambda) 6(n)/n$RT0.5 log n }, where k is the size of the pattern and n is the size of the sample set. Here, we give a sequential algorithm for the PSPM in R3 running in O[n2log n + kn1.8 log n (log*n)O(1)$RT time. Solutions to related problems are also discussed.