Jehyun Cha, School of Mechanical Engineering – Hanyang University, Joonghyun Ryu, Molecular Geometry and Voronoi Diagram Research Center – Hanyang University, Mokwon Lee, School of Mechanical Engineering – Hanyang University, Chanyoung Song, School of Mechanical Engineering – Hanyang University, Youngsong Cho, Molecular Geometry and Voronoi Diagram Research Center – Hanyang University, Paul Schumacher, US Air Force Research Laboratory, Misoon Mah, US Air Force Research Laboratory, Deok-Soo Kim, School of Mechanical Engineering – Hanyang University and Molecular Geometry and Voronoi Diagram Research Center – Hanyang University
Keywords: Space situational awareness(SSA), Conjunction prediction, Voronoi diagram, High-performance computation, Algorithm
Abstract:
Conjunction prediction is one of the critical operations in space situational awareness (SSA). For geospace objects, common algorithms for conjunction prediction are usually based on all-pairwise check, spatial hash, or kd-tree. Computational load is usually reduced through some filters. However, there exists a good chance of missing potential collisions between space objects. We present a novel algorithm which both guarantees no missing conjunction and is efficient to answer to a variety of spatial queries including pairwise conjunction prediction. The algorithm takes only O(k log N) time for N objects in the worst case to answer conjunctions where k is a constant which is linear to prediction time length. The proposed algorithm, named DVD-COOP (Dynamic Voronoi Diagram-based Conjunctive Orbital Object Predictor), is based on the dynamic Voronoi diagram of moving spherical balls in 3D space. The algorithm has a preprocessing which consists of two steps: The construction of an initial Voronoi diagram (taking O(N) time on average) and the construction of a priority queue for the events of topology changes in the Voronoi diagram (taking O(N log N) time in the worst case). The scalability of the proposed algorithm is also discussed. We hope that the proposed Voronoi-approach will change the computational paradigm in spatial reasoning among space objects.
Date of Conference: September 19-22, 2017
Track: Poster