Real-time detection and resolution of atom bumping in crystallographic models

A basic principle in crystal structure determination is that there should be proper distances between adjacent atoms. Therefore, detection of atom bumping is of fundamental significance in structure determination, especially in the direct space method where crystallographic models are just randomly generated. Presented in this article is an algorithm that detects atom bonding in a unit cell based on the sweep and prune algorithm of axis-aligned bounding boxes (AABBs) and running in $O(n \log n)$ time bound, where $n$ is the total number of atoms in the unit cell. This algorithm only needs the positions of individual atoms in the unit cell and does not require any prior knowledge of existing bonds, and is thus suitable for modelling of inorganic crystals where the bonding relations are often unknown a priori. With this algorithm, computation routines requiring bonding information, eg. anti-bumping and computation of coordination numbers and valences, can be performed efficiently. As an example application, an evaluation function for atom bumping is proposed, which can be used for real-time elimination of crystallographic models with unreasonably short bonds during the procedure of global optimisation in the direct space method.