Effectively organize locations by their geographical distance from a query point

Question

I am trying to find an efficient method, perhaps O (log (n)), finds a certain number of nearby locations at the request location based on their geographical coordinates (lat, lon).

The request point is not known in advance, but I can arrange other locations in advance to optimize the request.

Is there such a method or do I need to arrange and crop a list of all peers?

Answer 1

If your surface satisfies the triangle inequality, i.e. is a Euclidean space, the best algorithm for changing the spatial index is a space filling curve or a monster curve. It reduces problem 2d to task 1d and discretizes and solves the space address. Finding similar places is something like O (log (n)). You can find a good hilbert curve nick square blog article. I suggest also looking at n-ari monotonous gray codes. I wrote myself a php implementation, including a 4-direction Hilbert curve and a moore curve.