Comments: File is on castor
ContactPerson: boxer@niagara.edu
### Begin Citation ### Do not delete this line ###
%R 2001-01
%U /u0/csestaff/stock/head.ps
%A Boxer, Laurence
%A  Haralick, Robert
%T Even faster point set pattern matching in 3-d
%D January 09, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Point Set Pattern Matching, congruence,
%Y ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY; Geometrical problems and computations
%X Recent papers concerned with 
the Point Set Pattern Matching Problem (PSPM) 
(finding all congruent copies of a pattern in a sample set) 
in Euclidean 3-space, $R^3$, have given algorithms with 
running times that have decreased as known output bounds for the problem 
have decreased. 
In this paper, a recent result of Akutsu, et al., is used to show 
that the volume of the output is $O(kn^{1.8}[\log^* n]^{O(1)})$, 
where $k$ is the size of the pattern and $n$ is the size of 
the sample set. This is a smaller output bound than was previously known, 
and makes possible faster running times than were previously known for this 
problem. We show that with mild additional 
restrictions on the input (roughly, that the sample set is not too 
dense or the pattern set is not too small relative to the sample 
set), our solutions have running times bounded by the time to sort the volume 
of data given by our output bounds, on sequential computers and 
on a coarse-grained multicomputer (CGM). 
Solutions to related problems are also discussed.