nearest neighbor in 2D

[John Hunter]

>>>>> "Ron" == Ron Adam <radam2 at tampabay.rr.com> writes:

    Ron> I really don't know how you can make this faster.  There
    Ron> might be a library that has a distance between two points
    Ron> function that could speed it up.

If you only had to compare one point to all the other points, then the
brute force approach -- check every point -- will work great.  This is
O(N) and I don't think you can beat it.  The idea is that I will be
repeatedly checking and adding points to the list, so it is worthwhile
at the outset to set up a data structure which allows a more efficient
search.

The analogy is a binary search in 1D.  If you plan to repeatedly
search a (possibly growing) list of numbers to see whether it contains
some number or find the nearest neighbor to a number, it is worthwhile
at the outset to put them in a data structure that allows a binary
search.  Setting up the initial data structure costs you some time,
but subsequent searches are O(log2(N)).  See google for 'binary
search' and the python module bisect.

So roughly, for a list with 1,000,000 elements, your brute force
approach requires a million comparisons per search.  If the data is
setup for binary search, on average only 13-14 comparisons will be
required.  Well worth the effort if you need to do a lot of searches,
as I do.

John Hunter