Nearest Neighbor searching with Delaunay...

[Jonathan Shewchuk]

Michael Aupetit asks:
> Locating the nearest neighbor (NN) of a
> query point in a finite set of n reference points
> is in O(n). But if we construct the Delaunay
> triangulation of the reference points, then it
> should be easier to find the NN of any query
> point by marching along the graph structure from
> a current reference point to its neighbor which is the
> closest to the query, considering this as the new
> current reference, and iterating until no neighbors are
> closer to the query than the current reference
> (i.e. steepest descent onto the graph considering the distance
> between the current reference and the query).
>
> Is there any paper using this approach or theorem
> proving that using such steepest descent on the
> Delaunay triangulation leads to a unique global optimum?

I am not aware of such a paper, but there must have been one (if not dozens).
Here's a "proof" that you will find a global optimum (though obviously it
might not be unique).

It's well known that the Delaunay triangulation is isomorphic to the lower
convex hull of the "lifted" point set.  (Edelsbrunner and Seidel, Discrete &
Computational Geometry 1:25-44, 1986.)  The "lifting map" maps each vertex
v of the d-dimensional DT to a vertex (v, |v|^2) in d+1 dimensions.  The
downward-facing facets of the d+1 dimensional convex hull of the lifted
vertices correspond to the d-simplices of the DT.  (I have a picture of a
lifting map at the bottom of http://www.cs.berkeley.edu/~jrs/stab.html if
you want to get a clearer idea.)

So the procedure you describe is the simplex algorithm for linear programming.
For instance, take your DT, translate it so the query point is at the origin,
and apply the lifting map to the translated vertices.  Note that the height to
which each vertex is lifted, |v|^2, is its distance from the query point.
The goal is to find the lowest lifted vertex (i.e. the one lifted to the
least height) of the convex hull, which is a linear programming problem.

Jonathan Shewchuk


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.