In article <email@example.com .com>,
> 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
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:
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).