Subj : Re: Locating Nearest Neighbors in space (fast)
To   : comp.programming
From : Googmeister
Date : Thu Sep 08 2005 04:30 pm


Arthur J. O'Dwyer wrote:
>    If you're only dealing with two dimensions, you can compute the Delaunay
> triangulation of the set, and then /I think/ the nearest neighbor of any
> point must be one of its neighbors in the triangulation. Some caveats:
>   (a) I don't know if that's really true.
>
> I'd be interested to know whether this method would, in fact, work.

The dual of the Delaunay triangulation is the Voronoi diagram,
which essentially by definition solves the 2D problem. The Voronoi
lets you process a set of N Euclidean points in 2D and answer
queries of the form: given a new point (x, y) find a nearest neighbor.
Efficient algorithms solve both problems simultaneously in
O(N log N) preprocessing and O(log N) queries, but are nontrivial
to implement correctly.

I'm not quite sure what your defintion of "the set" and "one of its
neighbors in the triangulation" are (e.g., if you insert all 2N points,
its not true), but you are definitely correct in the close relation
between Delaunay and nearest neighbor.

.