Subj : Re: Locating Nearest Neighbors in space (fast)
To   : comp.programming
From : Arthur J. O'Dwyer
Date : Thu Sep 08 2005 02:57 pm


On Thu, 8 Sep 2005, KRK wrote:
>
> I'm programming in C
[...]
> 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!

(With different sets of points, I assume!)
   The first thing I thought of was "partitioning." Divide space into a 
bunch of cubes, and for each cube, get the set of points located inside 
that cube. Then for a point P in cube C, the nearest neighbor of P will
either be inside cube C, or inside one of the 26 neighbors of C,[1] unless
all 27 of those cubes are empty, in which case you'll need to look at
the 98 cubes next to the neighbors of C, and so on. (At some point, if P
is really lonely out there, you can just revert to brute force.)

[1] - Not strictly true, but I'm going to use the Knuth technique, in
which I'm allowed to lie in order to make the explanation of an algorithm
simpler. ;)


   If you're only dealing with two dimensions, you can compute the Delaunay 
triangulation of the set, and then /I think/ the nearest neighbor of any 
point must be one of its neighbors in the triangulation. Some caveats:
  (a) I don't know if that's really true.
  (b) If it's true, then it's probably a good algorithm for the average 
case, but it has terrible worst-case behavior.
  (c) I don't think it generalizes to three dimensions at all.

I'd be interested to know whether this method would, in fact, work.

HTH,
-Arthur

.