# Nearest Neighbor Search in Spherical Coordinates

I am familiar with k-d trees being used to find nearest neighbors (NN) in 3-D euclidean space however in my particular case I am given a huge array of spherical coordinates. Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates. Then given these points in their spherical coordinates how can I go about determining their NN. I need an algorithm that is efficient (relatively) and more importantly accurate.

EDIT: For sake of argument and for the philosophical point let's accept the 'loss of information' to quickly summarize my research in astrophysics does not allow me to simply convert to Cartesian coordinates and use a nearest neighbor algorithm due to the universe expanding and me dealing with something called redshift. TLDR: I cannot convert to cartesian and must use an algorithm in spherical coordinates for nearest neighbor.

• One option is to represent a point as two points with respect to two opposite azimuth directions. For each azimuth direction there is a separate spatial index. The point, ahem, is that for every point, there should be one index in which the "international date line" is far from the point. You can then interpret the spherical coordinates as Cartesian coordinates, find nearest neighbor in Cartesian, calculate maximum possible Cartesian distance of angular nearest neighbor, do Cartesian radius search with that distance, and find the point with smallest angular distance. Commented Oct 17, 2018 at 11:22