Subj : Re: Locating Nearest Neighbors in space (fast)
To   : comp.programming
From : Arthur J. O'Dwyer
Date : Thu Sep 08 2005 08:06 pm


On Thu, 8 Sep 2005, Googmeister wrote:
> 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.

(After a little Googling, I'm reasonably sure it is true.)

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

   Yep.

> I'm not quite sure what your defintion of "the set" and "one of its
> neighbors in the triangulation" are

   I mean, a Delaunay triangulation is a (planar) graph on the original set 
of vertices, where each face of the graph is a triangle. I'm claiming that 
to find the "nearest neighbor" of a point V, you can just brute-force 
search through all the neighbors of V in that graph, and you will find it.
   That's hard to parse because I'm using "neighbor" to mean two different 
things --- the "nearest neighbor" of V is the vertex closest to V in the 
Euclidean plane, but V also has a list of "neighbors" connected to it by 
edges in the Delaunay graph.
   I'm saying: The "nearest-Euclidean-neighbor" of V is one of its 
"Delaunay-graph-neighbors." So an exhaustive search of its 
Delaunay-graph-neighbors will find the nearest-Euclidean-neighbor, and
in most cases will be much, much faster than an exhaustive search of
/all/ the points.

> (e.g., if you insert all 2N points,
> its not true),

   I don't understand what you mean there.

> but you are definitely correct in the close relation
> between Delaunay and nearest neighbor.

-Arthur

.