Speaker
Description
Efficient collision detection and distance computation is essential for trajectory analysis, proximity operations, and long-term mission planning in space exploration. As datasets grow in scale and complexity—especially in asteroid tracking and satellite swarm coordination—there is a growing need for scalable algorithms that reduce computational load without compromising accuracy. Bounding volume hierarchies, particularly axis-aligned bounding box (AABB) trees, offer a powerful solution by hierarchically partitioning space using simple geometric approximations.
While AABB trees are well known for accelerating collision and proximity queries in low-dimensional Euclidean spaces $𝔼^2$ and $𝔼^3$, their potential in high-dimensional spaces is less explored. This contribution showcases two applications in high-dimensional spaces up to $ℝ^n$ (with $n ≫ 3$), using custom distance metrics tailored to astrodynamics problems.
The first involves clustering asteroids by trajectory similarity, where each asteroid’s orbit is represented as a sequence of $s$ 3D positions, forming a point in $ℝ^{3s}$. An AABB tree built in this space, combined with a trajectory-based metric, enables fast identification of asteroid groups following similar paths—offering a scalable alternative to more traditional but computationally intensive clustering methods.
The second example addresses the detection of close approaches between asteroid pairs over long time intervals—an important operation for mission planning and trajectory optimization. In this case, the AABB tree handles over 16000 dimensions, corresponding to position data sampled over a 15-year period, over a dataset of 60000 moving objects taken from last GTOC competition. The tree query to retrieve asteroid pairs' closest distance is completed in a fraction of second. This allows not only the detection of critical events such as potential transfer opportunities or collision risks but to identify the exact moment of closest approach.
These case studies demonstrate how AABB trees, typically used in graphics and simulation engines, can be effectively adapted to large-scale, high-dimensional problems in astrodynamics. Nonetheless, the underlying techniques are broadly applicable to tasks involving time-series similarity, high-dimensional clustering, and large-scale proximity search, highlighting the relevance of high-dimensional AABB trees for mission design, situational awareness, and navigation. This contribution, together with an available open-source C++17 implementation, provides a foundation for integrating advanced geometric search structures into future space exploration pipelines, enabling efficient handling of large datasets and complex queries.