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

[Edzer J. Pebesma]

Martin, gstat uses quadtrees for points in up to 3 dimensions; I think
that quadtrees are generally inefficient for higher dimensions, where
k-D trees are more efficient.

The gstat quadtree code is "burried" rather deep, and not available
as a simple R function (although it could be made as such).

Best regards,
--
Edzer

Martin Maechler wrote:

>We are looking for a fast algorithm (implemented in C or even
>available for R) to compute the k nearest neighbors of a given
>point from n points in R^4 (i.e. 4-dim. Euclidean space).
>
>Even more concretely, the n points in 4- space are in a (n x 4) matrix Y,
>and he has m other points in 4-space as (m x 4) matrix X
>
>The result should be an  (m x k) matrix Ik  where
>Ik[i,] contains k indices in 1:n with the meaning that
>Y[Ik[i,]] contains the k nearest neighbours of X[i,] in Y[,]
>
>A simply implementation {also the one used inside of the
>class package knn() function} will be of complexity O(m * n),
>but the fast algorithms known really should provide O(m * log(n))
>complexity.
>
>I see that packages 'gstat' and 'spatstat' mention solutions to such
>problems, but it seems this is just for 2-d point patterns, not
>4-d or "general dim" ?
>
>Pointers, hints, ... are very welcome.
>	
>Martin Maechler, Seminar fuer Statistik, 
>ETH (Federal Inst. Technology) Zurich,	SWITZERLAND   <><
>
>_______________________________________________
>R-sig-Geo mailing list
>R-sig-Geo at stat.math.ethz.ch
>https://www.stat.math.ethz.ch/mailman/listinfo/r-sig-geo
>  
>