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

Question

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.)

Answer 1

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.

2. 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.