# Algorithmic methods or techniques to find conjunctions in large ensembles of state vectors?

Suppose I wanted to answer the question Will Starman/Roadster pass particularly close to any asteroids in the next few years? or try to predict satellite conjunctions around Earth (e.g. Celestrak's SOCRATES), and I had ephemerides, TLEs, or interpolatable tables of state vectors.

I could propagate those in small time steps, calculate all $$N$$ positions and all $$N(N-1)/2$$ distances and search for any below a distance $$d_{conj}$$, but that might not be the most efficient way to do this.

Question: What are the algorithmic methods or techniques to do this kind of search more efficiently? Assume the propagators return a six-vector (position and velocity). I need an explanation or authoritative reference, not just a name-drop.

This question is distinct from Algorithmic methods or techniques to find conjunctions in high N Keplerian element ensembles? because it specifically asks about methods that operate on State vectors (either tabulated or propagated on demand) which may include n-body effects (e.g. the Sun moves, Jupiter does its thing, etc.)

• I have decided to re-ask this question based on this advice. I expect it to fly this time, rather than "conjunct" (collide) with its sibling question. – uhoh Dec 29 '18 at 6:21
• If I understand correctly that you ask about the closest pair of points problem in the six-dimensional Euclidean space, then this question is general enough to fit Math.SE. Or do you specify to anything related to orbital mechanics? – Everyday Astronaut Feb 8 '19 at 10:17
• Why are you interested in conjunctions of velocities? I.e. why do you include the 3 dimensions w.r.t. velocity in the state vector. The original Starman/Roadster question concerns the positions only. – Everyday Astronaut Feb 8 '19 at 10:20
• @EverydayAstronaut a conjunction is when two object reach a similar point in 4D spacetime $(x_c, y_c, z_c, t_c)$. I haven't asked about the velocities at $t_c$. However, to predict if that will happen at some point in the future, you need their two state vectors and two epochs $(x_1, y_1, z_1, vx_1, vy_1, vz_1, t_1)$ and $(x_2, y_2, z_2, vx_2, vy_2, vz_2, t_2)$. That's the minimal problem. My question is about an ensemble of $n$ state vectors and epochs $(x_i, y_i, z_i, vx_i, vy_i, vz_i, t_i)$ and looking at $O(n^2)$ pairs and predicting conjunctions for each one. – uhoh Feb 8 '19 at 13:26
• I thought you hat $n$ states $(x_i,y_i,z_i,vx_i,vy_i,vz_i)$ and want to find the closest pair of points among these $n$ points in 6 dimensions for each discrete point in time. Please help me with this 4-D setting. Which kind of metric do you use in that space for this purpose? Something like Minkowski? I mean you need to weight spatial and temporal distance. – Everyday Astronaut Feb 8 '19 at 14:54