A tree-based approach for efficient and accurate conjunction analysis

Michael Mercurio, Puneet Singla

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Conjunction analysis is the study of possible collisions between objects in space. Conventional conjunction analysis algorithms are geared towards computing the collision probability between any two resident space objects. Currently, there are few heuristic methods available to select which objects should be considered for a detailed collision analysis. A simple all-on-all collision analysis results in an O(N2) procedure, which quickly becomes intractable for large datasets. The main objective of this research work is to preemptively determine which catalogued objects should be considered for a more detailed conjunction analysis, significantly reducing the number of object pairs to be investigated. The heart of the approach lies in the efficient kd-tree algorithm. It has been found that this binary search method significantly reduces computational cost to a tractable complexity of O(N logN). The conventional tree-based search is modified slightly by accounting for probabilistic nearest neighbors via the Hellinger Distance. Finally, the method is extended to account for Non-Gaussian errors via the inclusion of Gaussian Mixture Models. It has been found that the reduced computational complexity of the kd-tree is maintained, while the applicability of the method is extended to uncertain cases.

Original languageEnglish (US)
Pages (from-to)229-256
Number of pages28
JournalCMES - Computer Modeling in Engineering and Sciences
Issue number3
StatePublished - 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Modeling and Simulation
  • Computer Science Applications


Dive into the research topics of 'A tree-based approach for efficient and accurate conjunction analysis'. Together they form a unique fingerprint.

Cite this