I do this all the time in AlignMix, our mapping package. Here's our super-fast algorithm:
1. Have a sorted list along one dimension (I normally do longitude)
2. Do a binary search to find the point with the closest longitude (let's call this P:0 ) and record the distance between this point and the search point
3. Start a loop: look at the next sequential point from P:0 in the sorted list; record the distance and update if smaller than previous; exit the loop if the difference in the longitude is now greater than the shortest distance found, otherwise move on to next point
4. Start a loop: look at the previous sequential point from P:0 in the sorted list: record the distance and update if smaller than previous; exit the loop if the difference in the longitude is now greater than the shortest distance found, otherwise move on to next point
In practice I combine steps 3 & 4 so it alternates searching for the next above and the next below P:0.
Hope that helps. In my tests this is extremely fast and scales the same as a binary search (log(n))
Steve