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).
Find k nearest neighbors on a sphere
data structures;computational geometry;nearest neighbour
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.