In article <1145427554.720375.287540@g10g2000cwb.googlegroups .com>,
David.Paterson@csiro.au says...
> Thanks from David Paterson. I've come to the conclusion that a "kd
> tree" is excellent if I want to find the approximate nearest neighbour
> (which is good enough for me) but not if I want the exact nerarest
> neighbour.

Not so. The k-d tree is the canonical data structure for exact
nearest neighbor queries (in low dimensions I should probably
add). The original reference is:

Friedman, Jerome. Jon Bentley. Raphael Finkel. =3FAn Algorithm for
Finding Best Matches in Logarithmic Expected Time.=3F ACM Transactions
on Mathematical Software, vol. 3, no. 3, pp. 209-226, September 1977.

You can find the technical report version of this paper here:

ftp://reports.stanford.edu/pub/cstr/.../482/CS-TR-75-
482.pdf

Their description leaves a bit to be desired, but the bottom line
is that, given a k-d tree implementation, the nearest neighbor
query can be implemented in about 10-15 lines of C/C++ code
(and probably not much more in Fortran).

I give an almost complete implementation in Section 7.3.7 of my
book; to be turned into an exact nearest neighbor query the code
just needs to be completed by shrinking the query sphere as
points are encountered (i.e. 1-2 lines of code).

--
Christer Ericson
http://realtimecollisiondetection.net/