I have about 200'000 data points distributed on the unit-sphere. Aside of each point's location on the unit-sphere, it has also assigned a width and height.

I can perform nearest-neighbor queries by placing the cartesian 3D coordinates of the points in a 3d kD-tree, since shortest cartesian distance also means shortest great-circle distance.

However, I would like to make queries of the form "get nearest neighbor of point p on the unit sphere, which has a width no more than w and a height no more than h"

So, two questions:

  1. I'm currently using a 3D kd tree for locations that would actually be constrained to a 2D surface. Is there a better option? I can't just use a 2D kd-Tree since there is no projection from the sphere to a plane that preserves point distances. Is there another option?

  2. What data structure can I use to make the kind of query described above efficiently?

  • $\begingroup$ You can project half a sphere to a plane (I'm not 100% positive this preserves the closest point, but I think it does). Do that 4 times (top half, bottom half, right half, and left half), and when you are queried about a point, do the query in the two kd-trees that the point resides in. About the width/height - you might want to incorporate a range tree too somehow. If I will come up with a more precise data structure that combines them - I will let you know. $\endgroup$
    – nir shahar
    Nov 25, 2021 at 14:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.