Fastest Nearest Neighbor Algorithm

[randumb]

Given a set of points, what is the fastest algorithm for finding the nearest neighbor of a single point? A flat-footed algorithm would take O(n), but there has to be an algorithm that can do it in O(log n). I've searched around in google a bit, but I'm not sure what algorithm is the best. I don't need a terribly complex algorithm, just something that can achieve O(log n).

The only nearest neighbor algorithm I'm familiar with is creating Voronoi diagrams, but that's only useful if I need to find the nearest neighbor of every point.

You can assume that the data set is static (won't be adding or removing points while running the nearest neighbor search).

Thanks a bunch!

 

[RaynorWolfcastle]

I don't see how it could be made faster than O(n), you need to check every point at least once regardless of your algorithm. O(log n) algorithms usually rely on some sort of order to remove points without needing to check them which you don't have here. I don't know, I'm kind of speaking out of my ass because I'm not a CS major, but this is my reasoning to say that O(log n) is as fast as you'll see for this.

edit: that should read O(n) is as fast as you'll see

 

[randumb]

Originally posted by: RaynorWolfcastle
I don't see how it could be made faster than O(n), you need to check every point at least once regardless of your algorithm. O(log n) algorithms usually rely on some sort of order to remove points without needing to check them which you don't have here. I don't know, I'm kind of speaking out of my ass because I'm not a CS major, but this is my reasoning to say that O(log n) is as fast as you'll see for this.

Oh, whoops.
I forgot to add that the points can be assumed to be sorted in the X or Y direction.

 

[TuxDave]

So isn't that more like a binary search?

 

[randumb]

Originally posted by: TuxDave
So isn't that more like a binary search?

What exactly would I be searching for? I don't know the closest distance.

 

[Creedyou]

Bellman-Ford or Djikstra algorithm? they might point in the right direction.

 

[randumb]

Originally posted by: Creedyou
Bellman-Ford or Djikstra algorithm? they might point in the right direction.

Hmm...aren't those shortest path algorithms?

 

[f95toli]

I still don't understand the question. How can the points be "sorted" in this case?

If you have a 2D problem. Lets say you have a point at (0,0) and you know it is surrounded by e.g. 4 points; unless you know the distances (in which case you have already solved the problem) there is no way to say which is the closest point without actually calculating the distance to each one (sqrt(x^2+y^2)) and then checking which is the smallest value.

Now, if the points where sorted with respect to the distance to (0,0) that would help; but again then you have already solved the problem.

 

[randumb]

Originally posted by: f95toli
I still don't understand the question. How can the points be "sorted" in this case?

If you have a 2D problem. Lets say you have a point at (0,0) and you know it is surrounded by e.g. 4 points; unless you know the distances (in which case you have already solved the problem) there is no way to say which is the closest point without actually calculating the distance to each one (sqrt(x^2+y^2)) and then checking which is the smallest value.

Now, if the points where sorted with respect to the distance to (0,0) that would help; but again then you have already solved the problem.

The nearest neighbor search is part of an algorithm for a game with unit groups. I have to run the nearest neighbor search many times, so its more efficient for me to sort the units by X or Y value beforehand and then use an optimized nearest neighbor search than to leave them unsorted and use a flat-footed method.

This might sound like I need a method for computing the nearest neighbor of all points, but the units can change groups, which means I would need to reconstruct a Voronoi diagram every time.

(The groups will stay sorted because when I move a unit from one group to another, I will insert it in its correct ordered place, which is only a O(log n) binary search)

I hope that makes sense.

 

[PTho9305]

In order to avoid looking at every point, the points need to be organized in some way. Here's how I would do it -

Make a bounding box, and break it into ( 40? 200?) equal squares. Each square stores pionters to the points currently in it. To look for the closest unit, first check for other units in your own square, then in those adjacent to you etc. When you find a square with other points in it, check all of them to find the closest.

Putting the points in the matrix will take 0(n) time. You only have to do this once, and because it is for a game, you can do it at the start of the game, then as units move you move them in the matrix = O(1).

Searching for the closest point to another will take... *drum roll* still O(n).
But in practice it will be much faster. It is O(n) because all the units could be in the same square, but if your squares are small enough, and units can't overlap, then you probably won't have more than 5 or 10 in a given square at a time, which would be O(1).

Oh, one problem. This doesn't work perfectly. Say you're looking for the closest point to 0,0. Each square in your matrix covers two units, from -1,-1 to 1,1. If there is a point at
.9,.9 this algorithm will say it is closer than one at 1.01, 0 which it is not. This can be avoided by searching one level past the one on which you find the first unit. But again, that still would not be perfect, it would just be wrong less often. I'm fairly certian this is the way StarCraft did it. You can watch the area you can view increase in small squares, not really in a circle.

Oh, and if I misunderstood the problem, and the points aren't going to be moving much at all, you can find the shortest path between *all* pairs of nodes in O(n) using some fancy but simple algorithm I forgot but have in my notes, and then look up the closest node in O(1) every time. But the moment any point moves you have to redo the O(n) part.

e-mail me with any questions - pst5@case.edu

 

[Peter]

The obvious optimizations I see are (A) to ditch the sqrt (not needed), and (B) to check whether (X^2) is already greater than current best before calculating (Y^2).

 

[Shalmanese]

Quadtrees would be one solution. Say you have a 100x100 area. You create a root cell that is sized 100x100. That root cell contains pointers to 4 child cells which are all 50x50 in size. Each child cell contains 4 child cells themselves and so on until you reach leaf cells which are, say, 0.1x0.1 units in size and contain the actual points. Cells are created on-demand, that is, unless there is a point inside that cell, it is not initialised. So to find the nearest point, you just traverse up the tree until you find a cell with more than 1 child. Most of the time, this will be the NN. To be completely certain, you have to do some more math to check whether you are on the edge of the cell and you might have to traverse another level. Depending on the density of the points and the size of the root cell, it should be fairly close to amortised O(1) or so to query, O(n log n) to insert as every point takes O(log n) to insert.

But seeing as your asking for multiple querys on a static data set, what's wrong with voroni diagrams? You get O(1) query at the expense of an expensive setup.