Optimal parameters for a hierarchical grid data structure for contact detection in arbitrarily polydisperse particle systems.

The objective of this paper is to find the optimum number of hierarchy levels and their cell sizes for contact detection algorithms based on a versatile hierarchical grid data structure, for polydisperse particle systems with arbitrary distribution of particle radii. These algorithms perform as fast as O(N) for N particles, but the prefactor can be as large as N for a given system, depending on the algorithm parameters chosen, making a recipe for choosing these parameters necessary. We estimate theoretically the calculation time of two distinct algorithms for particle systems with various packing fractions, where the sizes of the particles are modelled by an arbitrary probability density function. We suggest several methods for choosing the number of hierarchy levels and the respective cell sizes, based on truncated power-law radii distributions with different exponents and widths. The theoretical estimations are then compared with simulation results for particle systems with up to one million particles. The proposed recipe for selecting the optimal hierarchical grid parameters allows to find contacts in arbitrarily polydisperse particle systems as fast as the commonly-used linked-cell method in purely monodisperse particle systems, i.e., extra work is avoided in presence of polydispersity. Furthermore, the contact detection time per particle even decreases slightly with increasing polydispersity or decreasing particle packing fraction.