Nearest Neighbor searching with Delaunay...

[aupetit]

Hello,

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?

Thank you for your help.

Michael Aupetit





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