Filling domains with disks: an advancing front approach

An advancing front-based algorithm is proposed to constructively generate a random initial packing for disks with di erent radii within a 2D domain, which is often required in discrete element methods (DEM). Depending on whether the domain boundary is included in the initial front and how the front is formed, two di erent versions of the algorithm, termed the closed and open form, respectively, are presented. The open form version has an inherent linear complexity. The closed form can achieve the same complexity under a relatively weak condition. The generated packing is not a globally optimal arrangement but achieves a locally highest density from the algorithmic point of view. The performance of the algorithm is illustrated in several examples. The major bene t of this development is the significant reduction of CPU time required for the preparation of an initial discrete object con guration in DEM simulations. It is demonstrated that it takes only 3:77 s for the proposed algorithm to generate one million disks on a PC with a one 1 GHz processor