[Numpy-discussion] finding close together points.

[James Bergstra]

On Tue, Nov 10, 2009 at 8:17 PM, Christopher Barker
<Chris.Barker at noaa.gov> wrote:
> James Bergstra wrote:
>> In some cases a brute-force approach is also good.
>
> true.
>
>> If r is a matrix of shape Nx2:
>>
>> (r*r).sum(axis=1) -2 * numpy.dot(r, r.T) +
>> (r*r).sum(axis=1).reshape((r.shape[0], 1)) < thresh**2
>>
>> It's brute force, but it takes advantage of fast matrix multiplication.
>
> I'm more concerned about memory -- doesn't this use N^2 memory? Which
> could be an issue here.

Yes, this uses N^2 time and space.  It's not a good algorithm when N is large.

-- 
http://www-etud.iro.umontreal.ca/~bergstrj