On-line potato-sack algorithm efficient for packing into small boxes (Q1382412)

The subject of packing sequences of convex bodies was initiated by Auerbach, Banach, Mazur and Ulam, cf. Problem 10.1, in The Scottish Book [ed. by \textit{R. D. Mauldin}, Birkhäuser, Boston (1981; Zbl 0485.01013)]. Their corollary that one kilogram of potatoes can be put into a finite sack caused that results of this kind are sometimes called potato-sack theorems. By a box in \(E^d\) we mean any set of the form \[ \{(x_1,\dots,x_d); r_j \leq x_j \leq s_j \;\text{for} j=1,\dots,d\}, \] with \(r_j< s_j\) for \(j=1,\dots,d\). The number \(s_j-r_j\), where \(j\in\{1,\dots,d\}\) is called the \(j\)-th width of this box. By the height of this box it means the \(d\)-th width. The set \(\{(x_1,\dots,x_d); r_j\leq x_j \leq s_j\) for \(j=1,\dots,d-1\) and \(x_d=y_d\}\) is called the bottom of this box for \(y_d=r_d\) and the top for \(y_d=s_d\). If \(r_1=\dots=r_d=0\), the box is denoted by symbol \(B(s_1,\dots,s_d)\). The cube \(B(s,\dots,s)\) is denoted by \(I^d_s\). It is known that every \(d\)-dimensional convex body of diameter \(1\) and volume \(v\) can be moved into a convenient box of volume at most \(d!v\) and edge lengths at most \(1\) [see \textit{H. Hadwiger}, Elem. Math. 10, 122-124 (1955; Zbl 0066.40605) or \textit{A. Kosiński}, Coll. Math. 4, 216-218 (1957; Zbl 0083.38041)]. This result reduces the problem of packing sequences of convex bodies of diameters at most \(1\) to the problem of packing sequences of boxes of edge lengths at most \(1\) that can be packed. Then immediately can be obtained \(d!\) times smaller estimates for packing sequences of convex bodies of diameters at most \(1\). If \(s_1>1,\dots,s_d>1\), then the translative method of layers presented in \textit{M. Lassak} and \textit{J. Zhang} [Discrete Comput. Geom. 6, 1-7 (1991; Zbl 0727.52004)] permits packing every sequences of boxes of edge lengths at most \(1\) with total volume at most \((s_1-1)\prod^d_{j=2}(s_j-1)^2\) in \(B(s_1,\dots,s_d)\). The aim of this paper is to show an on-line algorithm for packing sequences of \(d\)-dimensional boxes of edge lengths at most \(1\) in a box of edge lengths at least \(1\). It is more efficient than a previously known method in the case when packing into a box with short edges. In particular, this method permits packing every sequence of boxes of edge lengths at most \(1\) and of total volume at most \(\left(1-\frac 12 \sqrt 3\right)^{d-1}\) in the unit cube. For packing sequences of convex bodies of diameters at most \(1\) the result is \(d!\) times smaller. The main result of the paper is enunciated as the following Theorem. Every sequence of boxes of edge lengths at most \(1\) and of total volume at most \(\left(1-\frac 12 \sqrt 3\right)^{d-1}\) \(\prod^d_{j=1} s_j=(0,1339\dots)^{d-1}\prod^d_{j=1} s_j\) can be on-line packed in the box \(B(s_1,\dots,s_d)\) with edge lengths at least \(1\).