nearest neighbor in 2D

[Isaac To]

>>>>> "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> and y in advance.

    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.