Efficient intersection detection between disks with identical radius

I have a set of $$N$$ points randomly positionned on a rectangular space (btw with either absorbing, reflecting or wrapping boundaries), and I need to obtain the distances between every 2 points whose distance is at most $$2\,r$$.

This is akin to consider every point as a disk with radius $$r$$ and only consider distances between centers of intersecting disks. I know that people doing collision detection are very much into optimizing the detection of intersecting shapes, but it seems that I can make hypotheses that they cannot make in general, and that would maybe help me not to test every 2 points together:

• There is no motion, only the set of static disks.
• All shapes are disks.
• All disks have the same radius $$r$$.
• I have a hint that the average distance between 2 neighbouring points is much smaller than $$r$$, so it will be frequent that numerous disks overlap together.

Are there clever ways to prune among the $$\left(\begin{array}{c}N \\ 2\end{array}\right)$$ pairs of points and (at best) only calculate distance between points whose disks are intersecting.. or likely to intersect together?

• This looks like a job for a spatial partition. Nov 11, 2021 at 14:32
• On top of @DMGregory's comment, given that the disks are static, a regular partition (i.e. splitting the rectangular space into a grid rectangles) may well be the most efficient method here. Ideally, you would use a grid where the cells are as close to square in shape as possible, and where the number of cells is roughly $N$. Nov 12, 2021 at 5:15
• @DMGregory Thank you, I'll have a look into this :) Nov 15, 2021 at 8:12
• @Pseudonym Thank you as well. Do you have any explanation why $N$ regular and squared cells would be the most beneficial? Nov 15, 2021 at 8:13
• @iago-lito Using $N$ cells means the space usage, and amortised search time, is linear. Using square-shaped cells makes the cell shape as close as practical to a circle, which is the shape that you actually want to search. Nov 15, 2021 at 14:08