1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

You can use Nearest. Your data:

SeedRandom[1]
data = RandomVariate[UniformDistribution[{0,1}],{20,2}];

Using Nearest to find all points that are within a distance of .1 to each element of data:

nf = Nearest[data->"Index", data, {All, .1}]

{{1, 2}, {2, 1}, {3}, {4, 15}, {5, 20, 12}, {6}, {7}, {8}, {9}, {10}, {11, 15}, {12, 5}, {13, 16}, {14}, {15, 4, 11}, {16, 20, 13}, {17}, {18}, {19}, {20, 5, 16}}

The above output says that points {1, 2} are close to point 1, points {2, 1} are close to point 2, point {3} is close to point 3, points {4, 15} are close to point 4, etc. Another example that may help:

Nearest[data -> "Index", data[[5]], {All, .1}]

{5, 20, 12}

which shows that points {5, 20, 12} are near point 5 (i.e., data[[5]]).

Obviously, we don't care that point 1 is close to 1, and similarly for the rest of the output, so we want to drop the first point in each set. We can use Part to eliminate these points:

indices = nf[[All, 2;;]]

{{2}, {1}, {}, {15}, {20, 12}, {}, {}, {}, {}, {}, {15}, {5}, {16}, {}, {4, 11}, {20, 13}, {}, {}, {}, {5, 16}}

Now, for any pair of points, one will have a lower index than the other. To avoid counting the pair twice, we can drop the cases where the nearest point has a smaller index. For example, the first set {2} says that point 1 has a near point of 2, and the second set {1} says that point 2 has a near point of 1. Since this is redundant, we'll subtract the first points index, and only keep the cases where the result is positive:

greaterSecondPoints = Pick[indices, Positive[indices-Range[20]]]

{{2}, {}, {}, {15}, {20, 12}, {}, {}, {}, {}, {}, {15}, {}, {16}, {}, {}, {20}, {}, {}, {}, {}}

Finally, we add the initial points as needed. So, {2} gets 1 added, {15} gets 4 added, {20,12} gets 5 added to each, etc.

Catenate[
    Thread /@ Thread[{
        Range[20],
        greaterSecondPoints
    }]
]

{{1, 2}, {4, 15}, {5, 20}, {5, 12}, {11, 15}, {13, 16}, {16, 20}}

Here is a function that encapsulates the above code:

nearPoints[data_, r_] := Module[
    {
    rng = Range @ Length @ data,
    n = Nearest[data -> "Index", data, {All, r}]
    },

    indices = n[[All, 2;;]];
    Catenate[
        Thread /@ Thread[{
            rng,
            Pick[indices, Positive[indices - rng]]
        }]
    ]
]

A larger sample set:

SeedRandom[2]
data = RandomVariate[UniformDistribution[{0,1}],{10^5,2}];

nearPoints[data, .01] //Length //AbsoluteTiming

{2.43175, 1558982}

$\endgroup$
5
  • $\begingroup$ I am not sure if I got it correctly, but this seems like it is doing $n^2$ operations. Do I miss something here? $\endgroup$
    – tst
    Oct 8 '18 at 22:42
  • 1
    $\begingroup$ @tst The Nearest function uses a KD-tree to find the nearest points, so it is pretty close to linear. The rest of the code depends on how many point pairs there are. $\endgroup$
    – Carl Woll
    Oct 8 '18 at 22:53
  • $\begingroup$ could you please explain a bit each line? :/ I cannot really understand what is going on. Why does this Nearest command do the job and how do I read the result? $\endgroup$
    – tst
    Oct 8 '18 at 23:27
  • $\begingroup$ @tst I tried to add more explanations. Hope it helps. $\endgroup$
    – Carl Woll
    Oct 8 '18 at 23:47
  • $\begingroup$ yes, thank you a lot for your help $\endgroup$
    – tst
    Oct 9 '18 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.