A precise algorithm to detect voids in polydisperse circle packings

作者：Specht Eckard

来源：Proceedings of the Royal Society A-Mathematical Physical and Engineering Sciences, 2015, 471(2182): 20150421.

DOI：10.1098/rspa.2015.0421

<jats:p>
Computer simulations are the primary tool for studying polydisperse particle packings quanti- tatively. For the problem of packing
<jats:italic>N</jats:italic>
unequal circles in a larger container circle, nothing is known
<jats:italic>a priori</jats:italic>
about the optimal packing (i.e. the packing with the highest packing fraction). Simulations usually start from a random initial configuration with the aim to finish with a dense final packing. Unfortunately, smaller circles often get stuck in trapped positions and prevent the rest of the packing from growing larger. Hence, the knowledge of the structure of unoccupied areas or
<jats:italic>holes</jats:italic>
inside a packing is important to be able to move trapped circles into free circular places or
<jats:italic>voids</jats:italic>
. A novel algorithm is proposed for detecting such voids in two-dimensional arbitrary circle packings by a decomposition of the contact graph. Combined with a clever object jumping strategy and together with other heuristic methods like swaps and shifts, this approach increases the packing fraction
<jats:italic>ϕ</jats:italic>
significantly. Its effectiveness for jumping across the maximally random jammed barrier (
<jats:italic>ϕ</jats:italic>
<jats:sub>MRJ</jats:sub>
≈0.8575 in the large-
<jats:italic>N</jats:italic>
limit) for small benchmark instances as well as for large problem sizes (up to
<jats:italic>N</jats:italic>
≈10
<jats:sup>3</jats:sup>
) is demonstrated.
</jats:p>

• 出版日期2015-10-8