[Solved]: Find k nearest neighbors on a sphere

Problem Detail: 

Given a set $S$ of $N$ points on a sphere, and another point $P$ on the sphere, I want to find the $k$ points in $S$ that are the closest (Euclidean or great circle distance).

I'm willing to do a reasonable amount of pre-computation. The solution must be exact and efficient (faster than linear time).

Asked By : JohnJ

Answered By : D.W.

Use the space partitioning approach to nearest neighbor search.

For instance, one approach is to use a $k$-d tree on on the surface of the sphere. You can express every point on the sphere using spherical coordinates: every point on the sphere has coordinate $(1,\theta,\phi)$. Thus, we have a 2-dimensional space with coordinates $(\theta,\phi)$. Now organize your points using a $k$-d tree, where here we are in $k=2$ dimensions. There are standard algorithms for nearest neighbor search in a $k$-d tree; heuristically, the expected running time is $O(\lg N)$.

You will have to make small modifications to the data structure to reflect that the coordinates "wrap around" modulo $2\pi$, but this is not hard. The key subroutine used in nearest neighbor search in a $k$-d tree is: given a point $P$ and a "rectangular" region $R$, find the distance from $P$ to the nearest point in $R$. In your case, the region $R$ is $[\theta_\ell,\theta_u] \times [\phi_\ell, \phi_u]$, i.e., the set of points $\{(1,\theta,\phi) : \theta_\ell \le \theta \le \theta_u, \phi_\ell \le \phi \le \phi_u\}$. It is easy to compute the distance from $P$ to the closest point in $R$. This will then let you use the standard algorithm for nearest neighbor search in a $k$-d tree.

Alternatively, instead of a $k$-d tree, you could use any other binary space partitioning tree, or you could look at metric trees, though I don't have any reason to expect them to be significantly better.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48128