MR linear contact detection algorithm

Large-scale discrete element simulations, as well as a whole range of related problems, involve contact of a large number of separate bodies and an efficient and robust contact detection algorithm is necessary. There has been a number of contact detection algorithms with total detection time proportional to N ln(N) (where N is the total number of separate bodies) reported in the past. In more recent years algorithms with total CPU time proportional to N have been developed. In this work, a novel contact detection algorithm with total detection time proportional to N is proposed. The performance of the algorithm is not influenced by packing density, while memory requirements are insignificant. The algorithm is applicable to systems comprising bodies of a similar size. The algorithm is named MR (Munjiza–Rougier: Munjiza devised the algorithm, Rougier implemented it). In the second part of the paper the algorithm is extended to particles of different sizes. The new algorithm is called MMR (multi-step MR) algorithm