Subj : Locating Nearest Neighbors in space (fast)
To   : comp.programming
From : KRK
Date : Thu Sep 08 2005 02:24 pm

Hi,

I'm programming in C and have two separate structure arrays holding 
coordinates for points in space

typedef struct{
    double x;
    double y;
    double z;
} Position;

Position *array1;        /*Approx. 50,000 Entries*/
Position *array2;        /*Approx 50,000 Entries*/

My problem is this, I want to take each point in array 1, and find its 
'nearest spatial neighbor' in array 2.  This can be done by brute force, but 
is rather slow, since to do this requires on the order of 10^10 multiplies. 
Further, I want to do this operation abot 180 times!

Does anyone know a fast algorithm to do this, preferably one that doesn't 
require fancy knowledge of data structures etc since I'm not a professional 
programmer.  Thanks.


Karl

.