Nearest Neighbor searching with Delaunay...
mast at sbox.tugraz.at
Tue Jul 9 11:05:23 PDT 2002
I'm not sure if I understand your intentions but I think that your
approach would not be useful: By building the Delaunay triangulation of
a point set you can easily obtain a point location structure which
allows to locate a new point in O(lg n) time.
Mark de Berg et al.
Computational Geometry - Algorithms an Applications
Micahel Aupetit wrote
> 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
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