[SciPy-dev] [Numpy-discussion] Proposal: scipy.spatial

[Prabhu Ramachandran]

Anne Archibald wrote:
> 2008/10/4 Prabhu Ramachandran <prabhu at aero.iitb.ac.in>:
>> In any case, I am not sure there is a general need for this kind of data
>> structure.  I need it a whole lot.  If there is a general need I'll be
>> glad to try and extract any of my code and contribute it to scipy.spatial.
> 
> There does seem to be a general need for a two-tree query that
> extracts (or just counts) all items of one tree within a ball centered
> at each item of another tree. You're right, too, that "in a ball"
> queries often don't naturally produce sorted results, or even known
> distances. But I think this has to be a different query. In fact, even
> for single-point queries it may make sense to have a separate query
> function for in-a-ball queries.

True and another reason for a different approach would be performance. 
According to Lee and Wong (1970, Acta Informatica) the worst case 
performance for partial region searches on k-d trees is O(k N^{1-1/k}). 
  So if the dimensionality is small and the region size is know we could 
do a lot better with other specialized algorithms for these cases.

cheers,
prabhu