Possible solutions how to find all points (given by lat, long) that are within a radius from main point

let's say that I have:

• M - Main point - given by coordinates (lat, long)

• C - Collection of points - also given by coordinates (lat, long)

• R - Radius - maximum search distance

I'm trying to find all points that are within a radius from main point (neighbors).

algorithm(main_point, collection_of_points, radius) --> neighbors


Obvious solution is to calculate distances and select those points, where distance is equal or smaller than R, but I believe there are better options with better performance.

Do you know any possible solutions? I'm open for every idea (not only the best one).

EDIT:

I should add that I'm looking for solution where points are strongly dynamic (every point is mobile phone or car). I'd like to update point when it's neccessary (it has been moved) so frequency of updates depends on amount of connected devices (so as queries). Let's say that server will get update request every 5 second and query request every 20 second.

Visualisation

You can speed up your search by using a datastructure like a kd-tree or an r-tree. The basic idea is to divide your space into boxes and store the mapping from points to boxes (and back) in a way that allows for quick lookup times. Then you don't have to calculate the distances to all points to see which are too far away, you can restrict your search to points in the same (or adjacent) boxes.

But note that the naive approach is actually pretty good in this case, even if it's asymptotically not optimal. CPUs are really good at summing squares and it's trivial to throw more cores at the problem if you need more speed. So unless you're dealing with many points, it will be hard to beat.

StackExchange Computer Science Q#64594, answer score: 2