Nearest Neighbor searching with Delaunay...
aupetit at dase.bruyeres.cea.fr
Mon Jul 1 12:41:35 PDT 2002
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.
The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce