Packing density of randomly deposited circles on a plane - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T23:33:25Z http://mathoverflow.net/feeds/question/63087 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63087/packing-density-of-randomly-deposited-circles-on-a-plane Packing density of randomly deposited circles on a plane unknown (yahoo) 2011-04-26T22:25:26Z 2011-04-27T06:20:37Z <p>Let's say that I have a rectangular two-dimensional surface of bounded dimensions, $[0,A]$ and $[0,B]$: </p> <p>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. </p> <p>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? </p> http://mathoverflow.net/questions/63087/packing-density-of-randomly-deposited-circles-on-a-plane/63091#63091 Answer by Anthony Quas for Packing density of randomly deposited circles on a plane Anthony Quas 2011-04-26T23:13:13Z 2011-04-26T23:13:13Z <p>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$. </p> <p>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$. </p> <p>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)$.</p> http://mathoverflow.net/questions/63087/packing-density-of-randomly-deposited-circles-on-a-plane/63092#63092 Answer by jc for Packing density of randomly deposited circles on a plane jc 2011-04-26T23:22:43Z 2011-04-26T23:22:43Z <p>The model you describe seems to fall under what's called <strong>"Random Sequential Addition"</strong> or <strong>"Random Sequential Adsorption"</strong> 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 <a href="http://rmp.aps.org/abstract/RMP/v65/i4/p1281_1" rel="nofollow">here</a>. From this review, I found <a href="http://www.springerlink.com/content/jh544tlk36x1n200/" rel="nofollow">a paper by Einar L. Hinrichsen, Jens Feder and Torstein Jøssang</a> 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.</p> <p>There's a newer review <a href="http://iopscience.iop.org/0953-8984/19/6/065124/" rel="nofollow">here</a> by A Cadilhe, N A M Araújo and Vladimir Privman.</p> <p>There's a ton of more recent work, but this should give you a place to start looking.</p> http://mathoverflow.net/questions/63087/packing-density-of-randomly-deposited-circles-on-a-plane/63119#63119 Answer by Sébastien for Packing density of randomly deposited circles on a plane Sébastien 2011-04-27T06:20:37Z 2011-04-27T06:20:37Z <p>If you are interested in a physicist's point of view on the question, you might like to look at <a href="http://cherrypit.princeton.edu/book.html" rel="nofollow">Random Heterogeneous Materials, S. Torquato</a>. It is now a little bit dated, but it provides a very extensive list of references.</p>