Finding all points in certain radius of another point

Question

I am making a simple game and stumbled upon this problem. Assume several points in 2D space. What I want is to make points close to each other interact in some way.

Let me throw a picture here for better understanding of the problem:

Now, the problem isn't about computing the distance. I know how to do that.

At first I had around 10 points and I could simply check every combination, but as you can already assume, this is extremely inefficient with increasing number of points. What if I had a million of points in total, but all of them would be very distant to each other?

I'm trying to find a suitable data structure or a way to look at this problem, so every point can only mind their surrounding and not whole space. Are there any known algorithms for this? I don't exactly know how to name this problem so I can google exactly what I want.

If you don't know of such known algorighm, all ideas are very welcome.

Answer 1

This is a range searching problem. More specifically - the 2-d circular range reporting problem.

Quoting from "Solving Query-Retrieval Problems by Compacting Voronoi Diagrams" [Aggarwal, Hansen, Leighton, 1990]:

• Input: A set P of n points in the Euclidean plane E²
• Query: Find all points of P contained in a disk in E² with radius r centered at q.

The best results were obtained in "Optimal Halfspace Range Reporting in Three Dimensions" [Afshani, Chan, 2009]. Their method requires O(n) space data structure that supports queries in O(log n + k) worst-case time. The structure can be preprocessed by a randomized algorithm that runs in O(n log n) expected time. (n is the number of input points, and k in the number of output points).

The CGAL library supports circular range search queries. See here.

Answer 2

This looks like a nearest neighbor problem. You should be using the kd tree for storing the points.

https://en.wikipedia.org/wiki/K-d_tree