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


Arthur J. O'Dwyer wrote:
> 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.

There are two sets of points (array1 and array2), say N of each.
If you take the Delaunay of all 2N, it might be the case that all
points
connected to V by a Delaunay edge are in the same array as V. In this
case, I didn't understand what your algorithm would do since the
OP wants the closest point in the other array. [I suspect now that
my confusion was because you aren't actually considering the two
set version.]

.