A direct lookup/calculation of all distances from a given point for every case would seem prohibitively expensive, agreed.
I'm sure there are more sophisticated ways to go at it, but you could start to reduce the search space by eliminating all which are farther away in either direction alone and only doing the full calculation within that grid.
You could in all likelihood reduce those distances by some sizable fraction and not miss the result -- say by sqrt(2)
