Finding all points in certain radius of another point

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.

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

Space partitioning is what you want.. https://en.wikipedia.org/wiki/Quadtree

You're still going to have to iterate through every point, but there are two optimizations you can perform:

1) You can eliminate obvious points by checking if x1 < radius and if y1 < radius (like Brent already mentioned in another answer).

2) Instead of calculating the distance, you can calculate the square of the distance and compare it to the square of the allowed radius. This saves you from performing expensive square root calculations.

This is probably the best performance you're gonna get.