Collision Detection Using Continued Fractions

Abstract

Context: In astronomy, collision detection is the computational problem of finding when planets, asteroids or satellites collide. Computer simulations make it possible to show very precisely how bodies move through space, which makes it possible to detect collisions. However, these simulations require a lot of computing power if there are many bodies, which is of course undesirable.
Aims: The aim of this report is to provide more insight into a collision detection method that does not use the computationally expensive simulations, but rather fast mathematical techniques.
Methods: It can be shown that the collision detection problem between two planets is equivalent to finding the integer point (𝑘, 𝑙) between two parallel lines, closest to the origin. The solution uses the continued fraction of the ratio of the orbital periods of the planets, as the slopes of the lines are this ratio. The convergents of the continued fraction form basis vectors with which the point (𝑘, 𝑙) is searched for. This is called lattice basis reduction.
Results: Where brute force always takes 𝑘 steps to find the integer point (𝑘, 𝑙), the method with continued fractions and lattice basis reduction often finds the point in about √𝑘 steps. The worst case however is still 𝑘 steps, the same as brute force. This only happens if there are no basis transformations, so luckily 𝑘 is then often small.
Conclusions: When there are many bodies between which collisions need to be detected, lattice basis reduction provides a fast method. For the basis vectors, the convergents of the continued fraction of the ratio of the orbital periods of the planets must be used. If the solution cannot be reached exactly, (𝑘, 𝑙) can also be estimated.