# Fastest way to find the closest point

I have a list in Python 2.7 of about 10000 point co-ordinates, like

``````[(168, 245), (59, 52), (61, 250), ... (205, 69), (185, 75)]
``````

Is there a faster way to search for all the points in a bounding box, instead of just iterating over the entire list each time and checking if the co-ord is inside the 4 sides??
I'm using this "algoritm" to see if any point, which is randomly moving, has come inside the stationary bounding box..(if it helps)

• How do you get these coordinates? Do they come one-by-one or all at once? And what language are you using? – superM Mar 13 '13 at 14:33
• @superM As tagged Python is my language. 2.7 to be exact. The co-ordinates are random... It's a list in python, so I can iterate and get one point at a time, but that is too slow for my purpose.. – pradyunsg Mar 13 '13 at 14:38
• It depends if your list is sorted or not. – Simon Bergot Mar 13 '13 at 14:39
• @Simon It's not sorted, how does that matter?? – pradyunsg Mar 13 '13 at 14:41
• are you able to put them into another data structure? – jk. Mar 13 '13 at 14:41

If the points are constantly moving, then it's impossible to do better than `O(n)`, because you have to check each point every time it moves. You have some code somewhere that moves the points, just add the bounds check into that code. Keeping a list sorted, or updating a quadtree or something would only be more efficient if the point positions were not changing frequently and instead you were checking several different bounding boxes, like searching for points on a map, for example.

If the points are moving according to a preset pattern, like in a straight line at a constant velocity, then you can change your algorithm to only do the bounds check when the direction or speed is changed. For example, if you are moving one pixel per second, and the bounding box is 10 pixels away, you know you don't have to check that point for another 10 seconds. 100 points is a pretty small number though, and at that small of a scale, the overhead from the extra complexity may not outweigh the extra iterations of the simpler algorithm.

Also, that small of a scale makes me wonder if you're sure the bounds checking is your bottleneck. A modern computer should be easily able to bounds check 100 points in under 10 microseconds. Have you actually measured it?

• +1 The edit adding "is constantly moving" really changed the question... – bunglestink Mar 13 '13 at 17:32
• I know, @bunglestink. It's interesting in our field how many "insignificant" details turn out to be critical. – Karl Bielefeldt Mar 13 '13 at 17:40

If possible I'd use a different data structure, one that is designed for spatial indexing. e.g. a quadtree (there are many others though)

This should allow (assuming non-degenerate data) to find a closest point in typicaly O(log n) comparisons. You could also use a spatial DB to do this for you .

edit: quadtrees really help when your points are (relatively) static to your search box, your edit suggests you have the opposite problem in which case you may not be able to do better than O(n) i.e. you probably dont want to construct a quadtree every time the points move unless you are going to be checking many bounding boxes for each move

• Is there anything like Quadtrees in Python?? – pradyunsg Mar 13 '13 at 14:51
• @Schoolboy if not, you can implement your own Quadtree in Python. It's a typical task as well as being a well-defined data structure which you can get plenty of documentation on. – Jimmy Hoffa Mar 13 '13 at 14:52
• there seems to be a pygame library that implements one and a few SO questions about implementing them (found via google), I doubt there is one in the standard library though, Spatial indexing is seen as a niche use – jk. Mar 13 '13 at 14:53
• +1, I was about to recommend a similar path. Depending on other constraints and how crucial this is, you could probably develop a very specialized data structure to get the lookup time close to O(1). Some info that would be helpful to optimize... can points repeat? are they over a set range? are they all integer values? – bunglestink Mar 13 '13 at 14:58
• @Schoolboy: First hit on Google: pypi.python.org/pypi/Quadtree. It's a C module, so if it works it'll be blazingly fast. – Martijn Pieters Mar 13 '13 at 15:23

As stated by you, there is no way of being faster than O(n). Every point in the list might be a hit, so you have to scan the entire list.

It would be possible to arrange the list such that you can terminate the search early if you can prove that none of the following points will be in the desired bounding box. For instance, by sorting the point by their X coordinates, you can stop searching when the value becomes higher than your upper boundary. Depending on what kind of point lists you get, other schemes may be more efficient.

• So in short, the answer is No, unless ... What other schemes? I'm using this "algoritm" to see if any point, which is constantly moving, has come inside the stationary bounding box..(if that shall help) – pradyunsg Mar 13 '13 at 14:49
• As Killian says, if you can keep the list in sorted order, you can halt iteration early. Sorting is roughly `O(n log n)`, but a sorted insert is only `O(log n)`. Keeping your points in a quadtree in the first place would be even better. – Useless Mar 13 '13 at 14:52
• The point is the algorithm and the data structure are tightly coupled. If you want a better algorithm, you need a better data structure too (counting a sorted list as a different structure because it's more constrained). Using a list with no additional constraint, iterating over the whole thing is all you can do. – Useless Mar 13 '13 at 15:00

What does "constantly moving" mean?

For example, if these points represent particles moving with a constant velocity and only affected by hard-sphere collision with other particles and with the wall, then it's possible to compute the time to intersection of each particle with the bounding box, and the compute the time for next collision. The time for next intersection can be kept in a priority queue, and when an intersection or collision occurs, you need only compute, in O(n) time, the next intersection of that particle/those particles with every other particle.

The mechanics of this are outlined in http://introcs.cs.princeton.edu/java/assignments/collisions.html , and summarized by Karl Bielefeldt earlier.

If the movement is random, but the changes are small and bounded then there's an upper limit on how far things can move. Use that as a bound. For example, if the max speed is 0.1 units per evaluation and your bounding box is the cell (10,10)-(11,11) then you can easily determine the particles within, say, 10 units of that cell, and know that there's no way any other particle can reach that cell for 100 evaluations.

If the coordinates change drastically each and every time, then the O(n) linear search is the best solution because any data structure (quadtree, hash grid, etc) takes at least O(n) time to set up, if only because it needs to visit each point.

• There's an edit.. – pradyunsg Mar 20 '13 at 13:32
• Thanks. "randomly moving" is not enough of a clarification. How is it random? I outlined an optimization you can do with "randomly moving" points, if there's an upper bound on the motion. To repeat, if there's no upper bound then there's nothing better than a linear search. At that point it's just a matter of optimizing your Python code, which you haven't shown. – Andrew Dalke Mar 20 '13 at 13:55