# 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? 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. 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. Feb 8 '19 at 14:54

Let's say you want to do something "reasonable", like collecting second-by-second conjunctions for a hundred year period, for all the objects you can get your hands on state vectors for (a hundred thousand or so?)

You have an $$O(S\cdot N^2)$$ approach, so... about $$\approx10^{20}$$

Yes, I can see there's a problem.

For the solar system, things move at limited speed. We can then take advantage of the fact that objects can only move so far each time step.

#### Here's a time partitioning algorithm:

1. Scan through your entire pile of state vector data to find the highest velocity. $$O(S\cdot N)$$. That should be an acceptable runtime, since you wouldn't even be able to store all those state vectors if it wasn't.

You'll end up with an extreme case, like the perihelion velocity of 1566 Icarus, on the order of ~100km/s. So for worst case relative velocity, objects moving directly towards eachother, we can assume an upper limit of about ~200km/s.

1. ##### Now, for each object, one at a time:

Do "rough" time steps, checking the distance to all other objects. Say, 10 days. That's six orders of magnitude less work than the granularity you are searching for.

In those 10 days, distances can at most close in ~1AU if relative velocities can be at most 200km/s.

Now, for the 10 "less rough" time steps inbetween of 1 day, only consider those objects within 1 AU in the "rough" time step. That will in many cases be a shorter list.

Inbetween that again, insert 10 "even less rough" timesteps of 2.4 hours. Here, we only have to consider those within 0.1 AU in the "less rough" time step. That should be a small minority of your state vector database.

At the ~15 min time step granularity, were down to running through the short 0.01 AU list. At 1.5 min, 0.001 AU.

If you stop the partitioning here, there will only be a couple of objects (or none!) to check for at every time step.

For objects distributed in a volume, or even clustered along a single 2D plane, this is asymptotically $$O(N^2)$$. That is, you don't have to worry about limiting how fine grained your time steps are.

Even for very nasty linear clustering (which doesn't apply to solar system objects by the way), this is still at worst $$O(log(S)\cdot N^2)$$

You should be able to sift through the pile in a couple of minutes on a laptop this way.