nearest neighbor in 2D

Kirk Strauser kirk at
Tue Nov 4 20:15:05 CET 2003

At 2003-11-03T04:12:47Z, John Hunter <jdhunter at> 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

More information about the Python-list mailing list