NBS contact detection algorithm for bodies of similar size

Large-scale discrete element simulations, as well as a whole range of related problems, involve contact of a large number of separate bodies. In this context an efficient and robust contact detection algorithm is necessary. There has been a number of contact detection algorithms with total detection time (CPU time needed to detect all couples close to each other) proportional to N ln(N) (where N is the total number of separate bodies) reported in recent years. In this work a contact detection algorithm with total detection time proportional to N is reported. The algorithm is termed NBS, which stands for no binary search. In other words, the proposed algorithm involves no binary search at any stage. In addition the performance of the algorithm in terms of total detection time is not influenced by packing density, while memory requirements are insignificant. The only limitation of the algorithm is its applicability to the systems comprising bodies of similar size. (C) 1998 John Wiley & Sons, Ltd.