nearest neighbor in 2D

[Graham Lee]

John Hunter wrote:

> 
> One solution that comes to mind is to partition to space into
> quadrants and store the elements by quadrant.  When a new element
> comes in, identify it's quadrant and only search the appropriate
> quadrant for nearest neighbor.  This could be done recursively, a 2D
> binary search of sorts....
> 

What happens when you put a particle in near/at the boundary of a quadrant
though?  It's possible for the nearest neighbour to be in the nearest
neighbour quadrant...although you could search over these as well. 
However, the number of independent areas implied by use of the word
'quadrant' suggests that this would be the same as iterating over all
space.... :-)
-- 
Graham Lee
Wadham College
Oxford