# Nearest neighbor search in latitude/longitude coordinates

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.

• Picking a point and calling it the north pole, you can map the complement of that point to the plane using, for example, the stereographic projection. The same use that you would do for those data structures on the plane, you can pull back to the sphere using the inverse of the projection. Either one chooses the north pole to not be one the points or the computations for that point could be done separately.
– plop
Oct 20 '20 at 23:03