9
$\begingroup$

The problem of the expected density of a saturated random packing of unit circles in the plane can be described as follows.

In a circular region $C$ of a large radius pick a point at random and draw a unit circle centered at the chosen point. Then pick another point in $C$ at random and draw again a unit circle, centered at the chosen point. If this circle overlaps with the previously drawn one, discard it and pick another point in $C$. Continue this process until the probability of finding one more point in $C$ for which the unit circle drawn about it does not overlap with any of the previously drawn circles is zero. The density of such packing of unit circles in $C$ is computed as the sum of the areas of the unit circles divided by the area of $C$. Let $d(C)$ denote the expected value of the density, and let $d$ denote the limit of $d(C)$ as the radius of $C$ tends to infinity.

Numerical experiments indicate that $d$ should be around $0.82$ (see for example https://www.sciencedirect.com/science/article/pii/0021979771903389), but, to the best of my knowledge, the exact value of $d$ is unknown. Are there any rigorous results obtained in this direction? Any reasonably good estimates, perhaps? Any references will be appreciated.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I think the process you describe is called RSA ("random sequential addition / adsorption"), see this answer mathoverflow.net/questions/63087/… . Note that the paper you link does not simulate RSA, instead their process applies some forcing to the circles. $\endgroup$
    – j.c.
    Commented Dec 16, 2017 at 18:24
  • $\begingroup$ Thanks for the reference on the earlier question. That question is, however, much more specific and difficult to answer, for it demands an answer for every specific finite rectangular container - a hopeless task. All I want here is the limit density value. $\endgroup$
    – Wlodek Kuperberg
    Commented Dec 16, 2017 at 18:40

2 Answers 2

Reset to default
5
$\begingroup$

Assuming that you're interested in random sequential addition / adsorption / deposition / packing (the random process described in the text of your answer) and not the process described in the paper you linked, here are a few relevant mathematical papers:

This 2001 paper of Penrose and 2002 paper of Penrose and Yukich show that the limiting density $d$ actually exists (not just in 2 dimensions); however I could not immediately see if their theorems lead to any explicit bounds on $d$.

This 1997 paper of Caser and Hilhorst give series expansions which lead to rigorous lower bounds for $d$; it seems the best they can do in the case you're interested in was $d>0.328$ (see Eq. 3.21).

(My answer that I linked in the comments above gives links to reviews in the physics literature which contain some discussion of estimates of $d$; I'll just reproduce the estimate $d\approx0.5472\pm0.002$ according to simulations described here).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ How is the discrepancy explained between the two estimates, 0.547 and 0.82...? $\endgroup$
    – Wlodek Kuperberg
    Commented Dec 16, 2017 at 21:30
  • 4
    $\begingroup$ As I said in my comment to your question (perhaps too obliquely), the estimate 0.82 in the paper you linked is not an estimate of the density of the process you describe in the text of your question. Here's the first line of the abstract of that paper: "A computer simulation study was made of the random packing of unimodal and bimodal circle size distributions under the influence of a weak central force." with italicized emphasis on the part that makes their model different from the one you ask about. $\endgroup$
    – j.c.
    Commented Dec 16, 2017 at 23:22
3
$\begingroup$

Following user @j.c.'s lead, here is another paper on RSA (Random Sequential Adsorption), which concludes with a density of $0.77$. From the abstract:

Abstract

Hinrichsen, Einar L., Jens Feder, and Torstein Jøssang. "Random packing of disks in two dimensions." Physical Review A 41.8 (1990): 4199. (Journal link.)

         
          Fig.2: The first iteration step.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ I am not sure how to resolve the discrepancies between the three quoted densities: $\{0.82, 0.77, 0.54\}$... $\endgroup$
    – Joseph O'Rourke
    Commented Dec 16, 2017 at 22:25
  • 3
    $\begingroup$ If you further compact a RSA configuration as mentioned in the abstract you screenshotted, it is no longer an RSA configuration. $\endgroup$
    – j.c.
    Commented Dec 16, 2017 at 23:18
  • 2
    $\begingroup$ (@j.c.:"screenshotted": Delightful new verb in the past tense! :-)) $\endgroup$
    – Joseph O'Rourke
    Commented Dec 16, 2017 at 23:47
  • 1
    $\begingroup$ "Screenshut" sounds sort of harsh :) $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Dec 17, 2017 at 5:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .