nearest neighbor in 2D

[G.J.Giezeman]

Isaac To wrote:

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

A solution in C++ is using the CGAL-library (www.cgal.org). Look in the 
index of the basic library and search for 'nearest'. It will point you 
to Delaunay triangulations, which, together with a triangulation 
hierarchy, will give O(log n) time complexity, except in pathological 
cases. You can call C++ code from python.
B.t.w., there will be a new release of the CGAL library very soon 
(probably this week).