Share Email Print

Proceedings Paper

Even faster point set pattern matching in 3D
Author(s): Laurence Boxer
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

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.

Paper Details

Date Published: 23 September 1999
PDF: 11 pages
Proc. SPIE 3811, Vision Geometry VIII, (23 September 1999); doi: 10.1117/12.364091
Show Author Affiliations
Laurence Boxer, Niagara Univ. and SUNY/Buffalo (United States)

Published in SPIE Proceedings Vol. 3811:
Vision Geometry VIII
Longin Jan Latecki; Robert A. Melter; David M. Mount; Angela Y. Wu, Editor(s)

© SPIE. Terms of Use
Back to Top