How can I do better than brute force in finding closest location?

Question

I have the following code:

public static Location findClosest(Location myPosition, ArrayList<Location> spots) {  
  double min = Double.MAX_VALUE;  
  Location closer = null;  
  for(MyPosition aPosition:spots) {  
     float dist = Math.abs(aPosition.distanceTo(myPosition));  
     if(dist < min) {  
         min = dist;  
         closer = aPosition;  
     }  
  }  
  return closer;  
}  

This is a brute force O(N^2) approach because this is called from the following function:

public static Location findClosest(Location myPosition, ArrayList<Places> places) {   
   Location closer = null;  
   double min = Double.MAX_VALUE;    
   for(Places place:places) {  
      Location currentMin = findClosest(myPosition, places.getSpots());  
      float dist = Math.abs(currentMin.distanceTo(myPosition));  
      if(dist < min) {  
         min = dist;  
         closer = currentMin;  
      }  
   }  
   return closer;  
}  

which for now works ok taking into account that the size of spots is not that big ~200 max.
What can I do to improve my approach?
Besides geohashing is there any other algorithm I could use for better performance?
Is there some property of coordinates I could use to skip some parts of my loop?

Answer 1

Because you said O(N^2), but this is a O(N) function, I'll assume you are calling this inside a loop to determine every point's closest. In that case, I don't know what would be faster.

However, to save yourself the trouble of having to run this function each time you want to store a closest point, add a HashMap of all the points to their closest, and check if the point is already added. If a new point gets added, only check it and all the original points against it.

Hope this helps, if only a little.