A fast multilevel algorithm for contact detection of arbitrarily polydisperse objects

An efficient algorithm for contact detection among many arbitrarily sized objects is developed. Objects are allocated to cells based on their location and size within a nested hierarchical cell space. The choice of optimal cell sizes and the number of hierarchies for best performance is not trivial in most cases. To overcome this challenge, a novel analytical method to determine the optimal hierarchical cell space for a given object size distribution is presented. With this, a decision can be made between using the classical Linked-Cell method and the contact detection algorithm presented. For polydisperse systems with size ratios up to 50, we achieved 220 times speed-up compared to the classical Linked-Cell method. For larger size ratios, even better speed-up is expected. The complexity of the algorithm is linear with the number of objects when the optimal hierarchical cell space is chosen. So that the problem of contact detection in polydisperse systems essentially is solved. (C) 2011 Elsevier B.V. All rights reserved.