TY - EJOU AU - Mercurio, Michael AU - Singla, Puneet TI - A Tree-Based Approach for Efficient and Accurate Conjunction Analysis T2 - Computer Modeling in Engineering \& Sciences PY - 2016 VL - 111 IS - 3 SN - 1526-1506 AB - 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. KW - PROBABILITY KW - COLLISION DO - 10.3970/cmes.2016.111.229