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

[Martin Maechler]

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