Open Access

ARTICLE

A Tree-Based Approach for Efficient and Accurate Conjunction Analysis

by Michael Mercurio¹, Puneet Singla²

1 Graduate Student, Department of Mechanical & Aerospace Engineering, University at Buffalo, State University of New York, Amherst, NY 14260-4400. E-mail: mjm95@buffalo.edu.
2 Associate Professor, Department of Mechanical & Aerospace Engineering, University at Buffalo, State University of New York, Amherst, NY 14260-4400. E-mail: psingla@buffalo.edu.

Computer Modeling in Engineering & Sciences 2016, 111(3), 229-256. https://doi.org/10.3970/cmes.2016.111.229

Abstract

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.

---

Keywords

---