[Numpy-discussion] finding close together points.

[Charles R Harris]

On Thu, Nov 12, 2009 at 10:01 AM, Christopher Barker
<Chris.Barker at noaa.gov>wrote:

> Peter Schmidtke wrote:
> > On Tue, 10 Nov 2009 16:07:32 -0800, Christopher Barker
> > <Chris.Barker at noaa.gov> wrote:
>
> >> I have a bunch of points in 2-d space, and I need to find out which
> >> pairs of points are within a certain distance of one-another (regular
> >> old Euclidean norm).
> >
> > How big is your set of points?
>
> Could be 100s of thousands, maybe ever millions. That's why O(N^2) is
> not good.
>
>
Another question is density. Are the points randomly scattered or do they
cluster? The order N^2 part can be taken care of if you can easily eliminate
a large fraction of the points, say by gridding the 2D part.

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20091112/bd2c7d43/attachment.html>