Closest Point to Moving Target

Question

I have a target which is constantly moving, and only its current position is ever known. I also have about one hundred objects surrounding it, and for each of these only the current position is known.

I am trying to find a more efficient way to find the closest object to my target at any given moment in time. I have looked at a bunch of algorithms, but none of them seem to fit this (nearest neighbor, closest pair of points, etc.).

My objects are unsorted. It does not need to be exact. The closest I have been able to think of is the brute force algorithm:

Objects objects = MyListOfUnsortedObjects();
Object closestObj = objects[0];
for each (Object obj in objects){
    if(obj is closer than closestObj){
        closestObj = obj;
    }
}
return closestObj;

Obviously, this is terribly inefficient. Would I be better off sorting and then dividing and conquering? Or am I way off base?

Any suggestions?

Answer 1

The solution is some form of spatial partitioning, which is arguably equivalent to "sort it and then divide and conquer", so you're not off-base at all.

There are many data structures used for this, such as quadtrees, BSPs, k-d trees, and so on. In my personal experience people normally recommend the quadtree as a good starting point.