Finding ponts closer to each other than a given distance

Discussion in 'Mathematics' started by tst, Oct 8, 2018.

1. tstGuest

As a working example let's assume that we are given a list of points in the unit square (say by RandomVariate[UniformDistribution[{0, 1}], {20, 2}]).

I want to find all pairs of points that their distance is smaller than r, (say 0.1).

The obvious way to do that is to check every pair of points. However this is $\frac12n(n-1)$ checks.

Is there any obvious (or not so obvious) way to speed this up?