Nearest Neighbor searching with Delaunay...

Martin Stettner mast 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
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
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list