Summary: [R-sig-Geo] Fast k-NN in R^4 ?

[Martin Maechler]

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

which points to http://www.cs.sunysb.edu/~algorith/files/nearest-neighbor.shtml
which 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