Nearest Neighbor searching with Delaunay...

[John Hershberger]

Michael Aupetit asks:
> 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?

Jonathan Shewchuk replies:
> I am not aware of such a paper, but there must have been one (if not dozens).
> Here's a "proof" that you will find a global optimum (though obviously it
> might not be unique).

....and then goes on to give a nice argument that the search procedure
is really the simplex algorithm on the convex hull of lifted points.

The idea of searching for nearest neighbors using the Delaunay
triangulation was used by Dickerson and Drysdale.  I've appended
relevant Geombib citations below.

--John Hershberger


@article{dd-frnns-90
, author =	"M. T. Dickerson and R. S. Drysdale"
, title =	"Fixed-radius near neighbor search algorithms for points and segments"
, journal =	"Inform. Process. Lett."
, volume =	35
, year =	1990
, pages =	"269--273"
, keywords =	"near neighbor search, Delaunay triangulation"
, update =	"93.09 drysdale"
}

@inproceedings{dd-ekdnp-91
, author =	"M. T. Dickerson and R. L. Drysdale"
, title =	"Enumerating $k$ distances for $n$ points in the plane"
, booktitle =	"Proc. 7th Annu. ACM Sympos. Comput. Geom."
, year =	1991
, pages =	"234--238"
, keywords =	"Delaunay triangulation, proximity, enumeration"
, precedes =	"dds-saeid-92"
, cites =	"aass-sdp-90, bfprt-tbs-73, c-ntcos-85, dd-frnns-90, s-mmdpsl-90t, sh-cpp-75, y-cmstk-82, ZZZ"
, update =	"97.11 bibrelex, 93.09 drysdale"
}

@article{dds-saeid-92
, author =	"M. T. Dickerson and R. L. Drysdale and J. R. Sack"
, title =	"Simple algorithms for enumerating interpoint distances and finding $k$ nearest neighbors"
, journal =	"Internat. J. Comput. Geom. Appl."
, volume =	2
, number =	3
, year =	1992
, pages =	"221--239"
, keywords =	"enumeration, selection, Delaunay triangulation, nearest neighbors"
, succeeds =	"dd-ekdnp-91"
, update =	"94.01 smid"
}


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