3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Reinstate Monica Oct 17 '18 at 11:22
2
$\begingroup$

Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates.

I don't understand this restriction. Converting to Cartesian coordinates uses essentially the same trigonometric functions that you would need to find the distance between two points in spherical coordinates: the only fundamental difference is that working directly in spherical coordinates you can take the cosine of the difference of azimuthal angles rather than taking sine and cosine of the individual azimuthal angles.

In any case, you should be able to bound the error in converting to Cartesian coordinates and take that error bound into account to create a shortlist of candidates using k-d trees; then recalculate the distances for the points in the shortlist using the spherical coordinates directly.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The algorithm is being used primarily in astrophysics research and due to the nature of an expanding universe it may not be completely accurate to use Cartesian coordinates instead of celestial coordinates ( spherical) so the restriction does have merit. $\endgroup$ – QuantumPanda Oct 17 '18 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.