A fast multilevel algorithm for contact detection of arbitrarily polydisperse objects

V. Ogarko, Stefan Luding

Research output: Contribution to journalArticleAcademicpeer-review

31 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)931-936
Number of pages6
JournalComputer physics communications
Issue number4
Publication statusPublished - 2012


  • METIS-294336
  • IR-80399


Dive into the research topics of 'A fast multilevel algorithm for contact detection of arbitrarily polydisperse objects'. Together they form a unique fingerprint.

Cite this