Packing density of randomly deposited circles on a plane

Question

Let's say that I have a rectangular two-dimensional surface of bounded dimensions, $[0,A]$ and $[0,B]$:

Under "no overlap" constraints, I sequentially deposit circles of radii $r_c$ on this surface, where the center-point of each circle is allowed real number coordinates and is chosen with uniform probability. To address concerns related to edge conditions, only the center-point of each surface needs to be on the bounded plane. If a set of random coordinates imply an overlap with one or more previously deposited circles, a new set of random coordinates is chosen. Under no conditions may any of the previously placed circles be rearranged.

Under these conditions, approximately how many circles, $N$, should I be able to pack onto the plane? What average-case maximum packing density is achievable?

Answer 1

The model you describe seems to fall under what's called "Random Sequential Addition" or "Random Sequential Adsorption" in the literature; it's viewed as a higher dimensional analogue of the car parking problem. An early review in the physics literature on this type of model by J W Evans is here. From this review, I found a paper by Einar L. Hinrichsen, Jens Feder and Torstein Jøssang which discusses continuum RSA of disks in the plane. Their simulations yield that for large A,B the fraction of space filled in the jammed state is around $\theta_J=0.5472\pm0.002$, from which you should be able to extract the answers to your questions.

There's a newer review here by A Cadilhe, N A M Araújo and Vladimir Privman.

There's a ton of more recent work, but this should give you a place to start looking.

Answer 2

The problem is essentially equivalent and slightly more symmetric if you make the rectangular surface "wrap around". (I'm assuming you want to have $A,B\gg r_c$?) You can of course also scale the problem so that $r_c=1$.

Assuming this the number of circles that you can place scales like $cAB$. I very much doubt that you can get a closed form for $c$, but you can get some simple bounds: Certainly $c\le 1/\pi$ (in fact you can get a better upper bound by looking at the best packing of discs in the plane: hexagonal tiling) so that you have $n\le AB/\pi$.

You can get a lower bound also: Supposing you've got a maximal packing of circles with centres $C_1,C_2,\ldots,C_n$. Then let $B_1,\ldots,B_n$ be discs of radius 2 about $C_1,\ldots,C_n$. These must cover the region (if any point is left out then you can add a new circle centred at that point without overlapping any of the original circles). Since they cover you get $4\pi n\ge AB$ so that $n\ge AB/(4\pi)$.

Answer 3

If you are interested in a physicist's point of view on the question, you might like to look at Random Heterogeneous Materials, S. Torquato. It is now a little bit dated, but it provides a very extensive list of references.