Is there a fast nearest neighbor search algorithm that generates the nearest neighbors, not based on Euclidean distances but based on geographic distances over a set of latitudes/longitudes. The fast nearest neighbor search based on Euclidean distances though is based on spatial indexing using R-Trees, K-D Trees etc. What about for Lat/Long distances?
On a sphere, you can use the nearest neighbor list from the Euclidean distance to get the correct points ordered by distance, because the Euclidean distance is less or equal to the geodesic distance. Once you have that list of points you can simply calculate the geodesic distance for the point of interest. So the fast k-nearest neighbor algorithms based on the Euclidean metric can be used.