1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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

0

Reset to default

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.