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:
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?
What data structure can I use to make the kind of query described above efficiently?