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.

Improve this question
$\endgroup$
1
  • $\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
    Commented Oct 17, 2018 at 11:22

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Oct 17, 2018 at 15:39
  • $\begingroup$ It seems to me that the astrophysical complexities of an expanding universe are irrelevant in this context. The cartesian coordinates you would be converting to are not the location of the distant astronomical object, instead, they are simply the (x, y, z) coordinates of a point on a theoretical sphere. There is a mathematical bijection between these Cartesian coordinates and the spherical coordinates. $\endgroup$
    – sligocki
    Commented Jan 7, 2021 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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