Nearest neighbor search in latitude/longitude coordinates

Question

I have two sets of lat/long points, $A$ and $B$. For each point $a$ in $A$, I want to find the corresponding closest point (by Haversine distance) $b$ in $B$. I'd like to use a space-partitioning tree, but as far as I can tell, quadtrees and k-d trees are confined to working in Euclidean space. How can I efficiently do a nearest-neighbor lookup in spherical space?

One solution I've considered is projection into 3d space and then using an octree, but I'd prefer not to do that if a space-partitioning tree (or alternative algorithm) that works with spherical coordinates directly exists.

Answer 1

First things first, if this is really a geography problem, then you probably don't want to calculate distances on the sphere, but rather on the reference ellipsoid. But even then, the reference ellipsoid is close enough to a sphere that it works as an approximation, and then accurate distances can be computed as appropriate.

You've already worked out that if all you need is nearest neighbour on points, then using 3D distance as a proxy for great circle distance is probably the most efficient approach. To be honest, this is probably the best solution for your specific problem, but not if you had to do distance queries involving non-point geometry (e.g. "find me all lines within 200km of this point").

The usual practice for spatial indexing in GIS is to use some variant on a bounding volume hierarchy.

In Cartesian space, that would mean an R-tree, and in geographic space, you would use circles of a sphere or ellipsoid as the bounding volume shape. In the case of a binary tree index, you can use a great circle as the splitting criteria for each node.