(190g) Improved Particle-Particle Contact Detection Using Efficient Data Structures

We revisited the No Binary Search (NBS) contact detection algorithm of Munjiza et. al. [ NBS contact detection algorithm for bodies of similar size, A. Munjiza and K. R. F. Andrews, International Journal for Numerical Methods in Engineering, Volume 43, Issue 1, Pages 131 - 149, 1998 ]. The outstanding feature of the NBS algorithm is that the total contact detection time is proportional to the total number of particles in the domain and that the outer loop is always over the total number of objects (and not over the number of bins). In the present work, we found out that the use of efficient data structures enables us to have an outer loop which will go over the total number of non-empty bins. Preliminary investigation shows that the resulting code is more than three times faster than our implementation of the algorithm of Munjiza et. al.