I have a question about the efficiency of an algorithm:

You have a list of x,y points

Now I want to get all the points that are up to 5 units away from a reference x,y point

How do you calculate it in the most efficient way?

I just go over each point and calculate distance, and if that distance is less than 5, I add it to the answer

If you know how this algorithm is called - I'd be happy if you post that too.

  • 1
    Nearest neighbor
    – user40980
    Nov 15, 2013 at 3:15
  • 1
    Many games work in x^2 space so that distance calculations can avoid expensive sqrt operations. Nov 15, 2013 at 3:58
  • You probably want to use a quadtree. Nov 15, 2013 at 4:12
  • 3
    @nurne: every algorithm has to visit each point just once, you cannot be more efficient. Of course, if you have to do the search more than once for different reference points, while the list of points is fixed, then the situation becomes different, and there is room for improvement. But you did not describe if that is your situation.
    – Doc Brown
    Nov 15, 2013 at 4:32
  • 2
    Notice that there is a difference between making an algorithm more efficient and choosing a more efficient algorithm.
    – Cephalopod
    Nov 15, 2013 at 12:26

3 Answers 3


While you cannot avoid having to check every point, there are techniques you can use to check quickly or check only once.

For example, most points you can tell if they are too far away without calculating the exact distance. For example, if I have a point whose x component is 100 away from the point of reference, you don't have to calculate distance. You already know that the point is too far away. Likewise if the x and y deltas are less than 5*2*sqrt(2) away from the point of reference, you know they are close enough. See the diagram below for a visual example:

Diagram describing algorithm

If P is your point of origin and the circle represents the farthest away that a point can be from point P (in your case radius of 5 units), then A and C represents places where points are definitely out or definitely in. Therefore, you can optimize your algorithm by checking x and y deltas. Only points which lie in the gray area B should have their distance calculated because you cannot know without performing a more sophisticated calculation.

Also, it would not hurt to sort your points by distance to P. If you have to perform this calculation often, you could optimize calculation by sorting once, then finding the farthest point within 5 units from P. Unless point positions change, you know that all points after that point must be closer.

I hope that helps!

  • OVerkill, really. The amount of extra code does not outweigh the small savings.
    – MSalters
    Nov 15, 2013 at 12:36
  • @MSalters I think trying to optimize for this sort of thing in general is overkill, however that is precisely what he is asking, and I am giving it to him.
    – Neil
    Nov 15, 2013 at 12:49
  • I'm fairly sure that this is not at all an optimization on any modern architecture. Yes, you do save some checks on y by checking x first, but that just does not make the code faster. x and y will be adjacent in memory, so they're probably both in the same cache line.
    – MSalters
    Nov 15, 2013 at 12:55
  • @MSalters The optimization was not "avoiding to read y". Please read my answer more carefully. The optimization is to be able to discard points with little more than a couple subtraction operations. You said it yourself in your own answer: "This saves you an expensive sqrt call per point", except my answer also saves you from having to square x delta and y delta as well. Also, I don't appreciate trying to put my answer in a bad light just so that your answer will get more reputation votes.
    – Neil
    Nov 15, 2013 at 13:10
  • 1
    @MSalters So you're talking about micromanaging pipeline stalls and unpredicted memory reads, and my answer is overkill? Also, I appreciate that you added your answer just to fix mine. That was very altruistic of you.
    – Neil
    Nov 15, 2013 at 16:41

This is a common problem, and there's exactly one known optimization for the one-shot case: check if the distance squared is smaller than 25. This saves you an expensive sqrt call per point. Squaring and adding coordinates is almost free, in comparison to the time it takes to retrieve the data from memory.


If you are going to be performing these tests repeatedly, then you should be able to get better that O(N) performance on average by holding the points in a quadtree.

Basically, a quadtree divides the 2D space recursively into a "tree" of nested squares (quads). Each square can have 4 nested squares, but you typically only subdivide a quad if there is something inside it.

Given a quadtree representation for the point list, you could find all points within 5 units from a given point as follows:

  1. Find the smallest quad that contains the 5x5 square around the nominated point. (Conceptually, you search the tree for the quad containing the square's 4 corners.)
  2. Iterate the points in that quad testing their distance from the nominated point.

The actual speedup will depend on the clustering of the points, and the granularity of the quads; i.e. when you stop the subdividing.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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