# Making an algorithm more efficient

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.

• Nearest neighbor – user40980 Nov 15 '13 at 3:15
• Many games work in x^2 space so that distance calculations can avoid expensive sqrt operations. – Steven Evers Nov 15 '13 at 3:58
• You probably want to use a quadtree. – Jerry Coffin Nov 15 '13 at 4:12
• @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 '13 at 4:32
• Notice that there is a difference between making an algorithm more efficient and choosing a more efficient algorithm. – Cephalopod Nov 15 '13 at 12:26

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: 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 '13 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 '13 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 '13 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 '13 at 13:10
• @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 '13 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.