nearest neighbor in 2D

[Kirk Strauser]

At 2003-11-03T04:12:47Z, John Hunter <jdhunter at ace.bsd.uchicago.edu> writes:

> 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.

Erm, no.  Imagine that your new point is in one corner of a quadrant.  The
other point in the quadrant is in the opposite corner.  There is a point in
the adjacent quadrant that is infinitessimaly close to your new point.
That's where your algorithm breaks down.
-- 
Kirk Strauser
The Day Companies