Name: Tanemura, M. (b. Shiga, Japan, 1946). 

Address:The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106-8569, Japan. 

E-mail: tanemura@ism.ac.jp

Fields of interest: Stochastic geometry, spatial statistics, mathematical crystallography
 
 

1 RANDOM CAR PARKING PROBLEM AND ITS EXTENSION

In 1958, a Hungarian mathematician, Alfréd Rényi, presented an interesting problem: "We place at random on the interval (0, ) unit intervals not having points in common. What is the expected number of intervals we can thus place on (0, )?". By assuming the unit interval a car on the road, the problem is often called "random car parking problem". Rényi (1958) solved this problem analytically and has obtained the solution .

As a simple extension of the random car parking problem, Rényi (1958) proposed a homothetic parking of unit cubes. Palásti (1960) conjectured from her computer simulations that the mean packing density  for D-dimensional space should have the following simple form = ,where is the solution defined above.

This relation = is quite appealing if it is true. Some people therefore have concentrated their attentions on ascertaining Palasti’s conjecture. Present status of this conjecture is presented in Solomon and Weiner (1986) and the deviations between experimental findings and Palásti’s conjecture are clearly shown there. These facts indicate that it is very difficult to treat the problem analytically for and that we are compelled to perform computer simulations.

Random sequential packing by spheres in -dimensional space can be thought of as another simple extension of the "random car parking problem". The procedure of random sequential packing of congruent -dimensional spheres is quite simple: The centre of the first sphere is uniformly sampled in the container and it is put there; and, in general, after spheres have been placed, the -st sphere is placed in such a way that its centre is uniformly distributed in the region which is occupiable for the centre, that is, in the set of points where the sphere does not overlap with any of the previously placed spheres. The process ends when there is no region available for a further sphere, and we call this final state a "random complete packing" (Tanemura, 1979). This kind of packing of spheres has many practical applications (see, for instance, Evans, 1993).
 

2 ALGORITHM FOR COMPLETE PACKING THROUGH VORONOI TESSELLATION

The most simple-minded algorithm which corresponds to the packing procedure stated above might be the following: the coordinates of the centre of a "test" sphere are determined by a random point which is uniformly distributed within the container. If the test sphere does not overlap with spheres already put, it is then put at that position. Otherwise, the test sphere is discarded and another test sphere is generated. The process is repeated until a certain stopping rule is fulfilled (hereafter, the total number of test spheres, , is used as a stopping condition: when the total number of test spheres exceeds , the procedure ends).

We call the above procedure of packing a "simple rejection scheme". It is seen that, by using only the simple rejection scheme, it is almost hard to attain a complete packing when the size of the container is adequately large compared with the size of each sphere. Figure 1 illustrates this circumstance (). Let the container be a square box whose size is where the unit of length is the diameter of packed disc . In Fig.1, is used. White 264 discs are put by using test discs, while dark seven discs and white ones are obtained for test discs. Black three discs in Fig.1 are not placed by test discs smaller than and they are actually obtained by the complete packing algorithm we present below. Note that the torus (periodic boundary condition) is used in this packing. Thus we take two stage strategy: (1) the stage of simple rejection scheme; and (2) the stage of complete packing.

2.1 Complete packing algorithm (CPA)

Let us assume, after the first stage of simple rejection scheme by using test spheres, k spheres are placed in the container . To each of , let us assign a large sphere whose radius is twice that of and concentric with . For this set of spheres, we perform the Voronoi tessellation. Then, the essential part of the complete packing algorithm (abbreviated by "CPA") is the followings:

Step B1. Detection of the position of occupiable space. By inspecting all of the Voronoi vertices, we can list up vertices which is not covered by any of . We call each vertex listed here an open vertex. If there is no open vertices, then CPA ends.

Step B2. Division and classification of occupiable regions. Here, all of the Voronoi edges are inspected by using open vertices.

Step B3. Placement of a new sphere into the occupiable region.

Step B4. Performing Voronoi tessellation for the new configuration of spheres. Go to Step B1.
 
 

Tanemura (1981, 1988a, b) had presented the random packing densities  and  for 2D and 3D spheres, respectively, in the limit by using CPA. Their estimates are 0.5474 0.0003 (95% int.) and 0.3809 0.0007 (95% int.), respectively. These values are comparable with those listed in Evans (1993).

The extension of CPA to higher dimensions is straightforward in principle. By using the computer programs for higher dimensional Voronoi tessellation used in Tanemura (2001), it is desirable to perform computer simulations of random sequential packing of 4D and 5D spheres.
 

References