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

[Nicholas Lewin-Koh]

Is that true?
You can construct the MST in O(n^2) given the distance matrix. Faster
if you allow some approximations. So that implies that all the extra 
time comes from calculating the distance matrix. For Euclidean distance
is it that bad to calculate the distance matrix? 

I will have to go check my copy of Okabe et al. and see what they mean.

Also, just a note on the listings from Stony Brook repository. Ranger is
part of a larger software instantiation, and not only is Leda huge it is
also semi-commercial. I used an old version of Roger's port a while
back, it was nice. Hope the license can be worked out.


Nicholas
 

>    1. Summary: [R-sig-Geo] Fast k-NN in R^4 ? (Martin Maechler)
> 
> 
> ----------------------------------------------------------------------
> 
> Message: 1
> Date: Fri, 9 Jul 2004 18:08:47 +0200
> From: Martin Maechler <maechler at stat.math.ethz.ch>
> Subject: Summary: [R-sig-Geo] Fast k-NN in R^4 ?
> To: R-SIG-geo at stat.math.ethz.ch
> Message-ID: <16622.49935.842914.315806 at gargle.gargle.HOWL>
> Content-Type: text/plain; charset=us-ascii
> 
> 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
> 
> 
> 
> ------------------------------
> 
> _______________________________________________
> R-sig-Geo mailing list
> R-sig-Geo at stat.math.ethz.ch
> https://www.stat.math.ethz.ch/mailman/listinfo/r-sig-geo
> 
> 
> End of R-sig-Geo Digest, Vol 11, Issue 2
> ****************************************