nearest neighbor in 2D

Isaac To kkto at csis.hku.hk
Mon Nov 3 06:16:00 CET 2003

```>>>>> "John" == John Hunter <jdhunter at ace.bsd.uchicago.edu> writes:

John> Given a new point x,y, I would like to find the point in the list
John> closest to x,y.  I have to do this a lot, in an inner loop, and
John> then I add each new point x,y to the list.  I know the range of x

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

By recursion your solution would work in O(log n) time.  The construction
would take O(n log n) time.  Unluckily, it can return the wrong point, as
the nearest point within the nearest quadrant might not be the nearest
point.

The problem is a well-studied basic computational geometry problem, although
I don't really know any Python code that actually do it.  Try to look at the
web for "Voronoi diagrams" and "radial triangulation" to understand how to
solve it properly in the above mentioned (perhaps randomized) time
complexity.

Regards,
Isaac.

```