Nearest Neighbor searching with Delaunay...

[Martin Stettner]

Hi,

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.

cf. 
Mark de Berg et al. 
Computational Geometry - Algorithms an Applications
p. 194f

kind regards

Martin Stettner

Micahel Aupetit wrote
> 
> 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.