9
$\begingroup$

Suppose one places unit cuboids of dimension $d$ with min-corners uniformly distributed to lie in $[0,n]^d$, but with cuboid (strict) overlap forbidden. At some point, the region is "saturated," without room for more cuboids to fit. For example, for $d=2$ squares in $[0,10]^2$, it appears that about $63$ squares on average will fit (whereas $n^d=100$ could fit):


  CubesPacking10
So here the packing density is about $63$%.

Q. Is the expected number of cuboids known, as a function of $n$ and of $d$? Is the growth rate in $n$ known for fixed $d$?


Update. Benjamin Dickman identified the $d=1$ version as the Rényi parking problem, where it is known that, for large $n$, the packing density approaches $m \approx 0.7476$, i.e., the expected number of cars(intervals) is $m n$. It is conjectured that in $d=2$, the expected packing density approaches $m^2 \approx 0.559$.

Yoav Kallus points to a related paper that uses the apt phrase sequential random packing for the process.

$\endgroup$
3
  • 3
    $\begingroup$ Is it possible that you are asking a question equivalent to an extension of the parking problem? Cf. mathworld.wolfram.com/RenyisParkingConstants.html $\endgroup$ Nov 8, 2014 at 3:01
  • 3
    $\begingroup$ A (1) discrete version (2) on a torus (3) in higher dimensions is treated in this preprint: arxiv.org/abs/1410.0839 . Maybe it could be informative despite the many differences. $\endgroup$ Nov 8, 2014 at 3:01
  • $\begingroup$ More generally, I believe what you want is the random sequential adsorption for a system of parallel cuboids. Here is a brief paper that refutes the $d=2$ (Palasti) conjecture (as do several other numerical works) and provides some citations/terminology that you may find of interest: journals.aps.org/pra/pdf/10.1103/PhysRevA.43.631 $\endgroup$ Nov 8, 2014 at 18:08

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.