Performance comparisons of tree-based and cell-based contact detection algorithms

Purpose - The main purpose of this paper is to compare the performance of three commonly used global search algorithms, namely tree-based augmented spatial digital tree, cell-based no binary search and D-cell, in the discrete element simulations. Design/methodology/approach - A large number of test cases with up to five million particles/discrete objects are employed to numerically examine the computational costs of the three search algorithms and their performance is compared. Findings - Comprehensive comparisons reveal that the D-cell is more efficient than the tree-based search algorithms for large-scale problems. The parametric study of the D-cell algorithm itself shows that the performance of the algorithm is strongly dependent on the cell dimension chosen. Research limitations/implications - The only limitation of the current work is that the tested domain shape is regular, and thus more complex domain shapes may need to be considered. Originality/value - The paper provides clear guidance regarding the possible actual computational performance of the tested search algorithms for practical applications.