Summarizing the reactions & findings to my question:

1) Timothy Keitt said:

This is a really good resource:

http://www.cs.sunysb.edu/~algorith/major_section/1.6.shtmlwhich points to

http://www.cs.sunysb.edu/~algorith/files/nearest-neighbor.shtmlwhich then mentions implementations ANN, Ranger, LEDA, (and

less relevant ones). Ranger seems a standalone visualization.

LEDA is well known but a bit "big" for me which leaves ANN, see

below.

2) Roger Bivand has an experimental version of an R package

'ann' which interfaces to ANN mentioned above, aka,

http://www.cs.umd.edu/~mount/ANN/
Note that "A" stands for "Approximate", but the software can

also compute the exactly k-NN solution.

Roger sent me the package privately and is currently travelling for a

while. I hope that I will be eventually encourage him (:-)

to release 'ann' to CRAN. AFAIK, one major obstacle has been the

non-standard copyright/licence and the difficulty to make

contact with the ANN authors.

3) Frank Hardisty has been interested in the related problem of

'MST in arbitrary dimensions' where he said he found

``that there is no known MST solution that is better than O(n^[R/2]+1,

where n is the number of points and R the number of dimensions.

Which is fairly awful. The reference is: Okabe, A., B. Bots,

K. Sugihara and S. N. Chiu (2000). Spatial Tesselations. NY, Wiley.

It's a good book. ''

(and he also attached relevant papers which I haven't studied yet).

My conclusion here: The multivariate MST seems a harder

problem than finding multivariate k-NN.

----

Conclusion: I hope (with good reason) that there will soon be an

R package 'ann' (or similarly called) interfacing to ANN.

Thanks again for your support!

Martin Maechler, ETH Zurich