[R] Traversing KD-tree (or equivalent) for radius-based search

[Andrea Taverna]

Hi,

I'm trying to implement the DBSCAN algorithm to get O(N*LogN) complexity 
and I'd need a spatial tree of some sort (kd,r,bd..), or a function that 
computes radius-based search on spatial data, i.e. given a radius eps 
finds ALL the points which fall in the corresponding hypersphere 
centered on the current examined point.  Is there a package with this 
features?

So far I found RANN and other packages whose name I can't remember (I 
don't have them with me a.t.m.), and they all seemed to offer a 
nearest-neighbour search, which asks for an upper limit to the number of 
points to be found, but no direct access to the spatial tree they used . 
The algorithms they provide are built around that limit and setting it 
to large values makes their execution impractical.
OTOH, as far as I have understood, DBSCAN needs to know all the points 
in the eps-neighbourhood, or will create too many clusters, especially 
if there are really high-density region, as it happened when I used 
RANN's nn2 function in my implementation.

thanks in advance,

Andrea Taverna