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

Abstract

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.

Citation

Han, K., Feng, Y.T. and Owen, D.R.J. (2007), "Performance comparisons of tree‐based and cell‐based contact detection algorithms", Engineering Computations, Vol. 24 No. 2, pp. 165-181. https://doi.org/10.1108/02644400710729554