DIGITAL MODELING OF RANDOM PACKINGS OF SPHERES OF EQUAL DIAMETERS WITH LOW PACKING DENSITY

V. A. VOROB'EV, V. K. KIVRAN, I. E. NAATS

(Submitted by the scientific seminar of the UVL)

In modeling random packings of spheres with very low packing density, when the sizes of the spheres may be neglected in comparison with the distances between neighboring spheres, the spatial distribution of the packed spheres may be replaced by the distribution of points coinciding with the centers of the spheres. In this case, with uniform filling of space, the probability distribution of the number of points (spheres) in some volume obeys the Poisson distribution law, and the modeling of such packings may be replaced by the generation of three-dimensional random numbers with a uniform distribution law, which are the centers of the packed spheres. To obtain denser packings of nonintersecting spheres, it is necessary to check for intersections of spheres and to exclude intersecting spheres from the packing. The random character of the packings in this case does not change; only certain deviations appear in the spatial distribution of the spheres from the Poisson law.

A model of the indicated packing on digital electronic computers (DECs) may be obtained by the following algorithm. The packing of spheres is carried out sequentially, one sphere at a time; moreover, when the next sphere is packed, the positions in space of the previously packed spheres are not changed. Let the coordinates of the centers of the already packed spheres be stored in the memory of the DEC. To pack the next sphere, a three-dimensional random number with a uniform distribution law is generated [1]. Then the center of the sphere is placed at this point, and the possibility of intersection of the sphere being packed with other, previously packed ones is checked. For intersecting spheres, the distance between the centers of the intersecting spheres must be, in magnitude, not less than the diameter of the sphere (spheres of equal size are being packed). If the sphere being packed does not intersect with any previously packed one, the sphere is considered packed, and its coordinates are recorded in the memory of the DEC. If, however, the sphere being packed intersects with at least one previously packed sphere, it is considered that the center of the sphere being packed cannot be placed at the given point; a repeated attempt is made to pack the given sphere by a new drawing of a three-dimensional random number and an analogous check.

The packing algorithm described above can be implemented on a DEC by means of a program compiled according to the block diagram given below (Fig. 1). According to this block diagram, spheres are packed in a cube located in the first octant of a rectangular coordinate system, one

from one of whose vertices the origin of coordinates is located. The diameter of the sphere \(d\) is measured in fractions of the length of the cube edge; therefore the length of the cube edge is equal to unity. According to this flowchart, a specified number \(n\) of spheres with a specified diameter is packed.

Fig. 1. Flowchart of the program for random packing of equal spheres with low packing density

During the packing of spheres, a moment is possible when not a single additional sphere can be packed without intersecting spheres packed earlier (under the condition of the algorithm, their spatial position cannot change). To detect this moment, the following is provided in the flowchart. In practical testing of this algorithm on a digital computer it was established that, when packing spheres of diameter 0.1, after 1000 unsuccessful attempts to pack the next sphere, the probability that it can nevertheless be packed in subsequent attempts is negligibly small. Therefore, in the present flowchart it is assumed that if a sphere is not packed in \(1/d^3\) attempts, the packing process is stopped. For the same reason, the operation of the program according to this flowchart for packing each \(j\)-th of the \(n\) required spheres begins with the organization of the down counter \(N_1\) (block 1); at each unsuccessful attempt to pack the next sphere, one is subtracted from it.

Next follows the drawing of a three-dimensional random number (block 2)—the center of the sphere being packed—and a check for intersection of the sphere being packed with the faces of the cube (block 3). If, for each coordinate, the condition

\[ r \leq x_i \leq 1-r,\qquad i=1,2,3, \tag{1} \]

is satisfied, where \(r\) is the radius of the sphere, then the faces of the cube cannot intersect the sphere being packed, and the center of this sphere may take the previously drawn random coordinates. If condition (1) is not satisfied, the drawing of coordinates is repeated. Such a manipulation does not violate the law of uniform distribution of the random numbers; only the range in which they are represented is reduced on each side by the value of the sphere radius.

Next, the sphere being packed must be checked for intersection with previously packed spheres. If, for all spheres, the condition

\[ R_k^2 = (x_1 - x_{1k})^2 + (x_2 - x_{2k})^2 + (x_3 - x_{3k})^2 \ge d^2, \tag{2} \]

\[ k = 1, 2, \ldots, j - 1, \]

is satisfied, then the sphere with coordinates \(x_1\), \(x_2\), and \(x_3\) can be packed without intersecting the previously packed spheres. Here \(x_{1k}\), \(x_{2k}\), \(x_{3k}\) are the coordinates of each of the \(j - 1\) previously packed spheres. Verification of condition (2) is carried out in two stages. First (block 7), the conditions

\[ |x_i - x_{ik}| \ge d, \tag{3} \]

\[ i = 1, 2, 3, \]

are checked, which automatically entails satisfaction of condition (2) when at least one of these conditions is satisfied; this means that the two given spheres do not intersect. In this case, verification of condition (2) becomes unnecessary, and verification of conditions (2) and (3) begins for the next of the \(j - 1\) spheres (via block 10). If all conditions (3) are satisfied for the \(k\)-th sphere, the quantity \(R_k^2\) is computed (block 8) and condition (2) is checked (block 9). If this condition is satisfied, i.e., the sphere being packed does not intersect the \(k\)-th sphere, verification of conditions (2) and (3) begins for the next sphere.

If the sphere being packed does not intersect any previously packed sphere, and all conditions (2) are satisfied, the sphere is considered packed, and its coordinates are recorded in the corresponding memory array of the digital computer (block 4). If, however, at least one of conditions (2) is not satisfied, a repeated attempt is made to place the sphere by drawing a new three-dimensional random number (block 2), after first subtracting one from counter \(N_1\) (block 11). When counter \(N_1\) is completely cleared (block 12), the filling process is stopped (block 13); the so-called saturation of the packing occurs.

The program based on the above-described flowchart was tested on the M-20 digital computer with sphere diameter 0.1. The packing process continued until saturation. In different experiments the number of spheres in the packing reached \(473 \div 506\), which corresponds to a packing density (the ratio of the total volume of all packed spheres to the volume of the cube being packed) of \(0.248 \div 0.265\). The time required to pack this number of spheres (to saturation) was from 4 to 8 min. The time required to achieve a packing density of 0.2 in the same cube is no more than 2 min.

It should be noted that the maximum value of the so-called filling density, which is meaningful for a large number of spheres or for packing in a large volume, must be somewhat higher, since the figures given above do not take the boundary effect into account.

REFERENCES

1. D. I. Golenko. Modeling and Statistical Analysis of Pseudorandom Numbers on Electronic Computing Machines. Nauka Publishing House, Moscow, 1965.