Algorithmic methods or techniques to find conjunctions in high N Keplerian element ensembles?

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 simple Keplerian orbital elements, not necessarily osculating element tables nor first time derivatives of the elements (though an answer about that would be great!)

I could propagate those simple one-body Keplerian orbits 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? 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 large ensembles of state vectors? because it specifically asks about methods that operate on Keplerian elements. For example, in the case of simple Keplerian elements, you can immediately rule out some combinations at the beginning if one's periapsis is more than $d_{conj}$ larger than the other's apoapsis.

Answer 1

Propagating $N$ objects and checking $N(N-1)/2$ distances at each small time step is indeed computationally inefficient to the point of being impractical. If I recall correctly, there are currently ~17000 catalogued objects on SPACE-TRAK. Assuming to check for collisions every second,* we would have to compute $10^{13}$ Euclidean norms in a single day. Some kind of filtering is absolutely necessary.

I believe that the work of Hoots, Crawford, and Roerich (1984) is one of the earliest and most frequently cited approaches to the problem. I'm not confident with the details, but I believe it consists of 3 steps, with increasing degree of refinement:

1. An apogee-perigee filter, in which concentric orbits are excluded,
2. A geometric filter, in which the minimum distance between the orbits is checked to be under a certain threshold,
3. A timing filter, in which the objects on the orbits that pass filters 1 and 2 are checked to be close to the same point at the same time.

Such a filter probably still gives quite a lot of false positives, and those will have to be checked by computing the Euclidean distance between them. Other factors to be considered are A) that Keplerian orbits are a valid approximation for only a limited time span from the last orbit determination, and an accurate trajectory obtained through numerical propagation is usually needed; and B) that the uncertainty in the position/velocity of the objects has to be taken into account, ultimately determining collision probability.

Anyway, I think that this is an active line of research still today. You can find more approaches in the citations to the Hoots et al. paper, but I believe that most of them still boil down to improved sequential filtering approaches (which can be performed in parallel for large numbers of objects).

---

* Also, 1 second is way too large to check for collisions. LEO spacecraft have relative speeds in the order of 10km/s, so using a 1-second interval would miss most of the collisions.