On-line and q-adic Packing Sequences of Segments, Cubes and Boxes

Abstract: We present an on-line algorithm for packing sequences of cubes of edge lengths at most $1$ in a $d$-dimensional box, and, in particular, in the cube $I^d_s$ of edge length $s$. The algorithm guarantees that if a successive cube from a sequence cannot be packed, then the volume of the unfilled part of $I^d_s$ is at most a number of the order of magnitude $s^{d - d/(d+2)}$. As $d \to \infty$, this order of magnitude approaches the analogous order $s^{d-1}$ in the best known off-line method. We also show a similar method for on-line packing sequences of boxes. Moreover, we prove that if $D$ is a box with integer edge lengths and if $q \geq 2$ is an integer, then every sequence of boxes of edge lengths from the set $\{ q^0, q^{-1}, q^{-2} \dots \}$ and of total volume at most ${\rm Vol}(D) - q[({q \over {q-1}})^{d-1} -1]$ can be on-line $q$-adic packed in $D$. If all the boxes are assumed to be cubes, then the packing is possible provided the total volume is at most ${\rm Vol}(D)$.

Classification (MSC91): 52C17

Full text of the article:

• Compressed DVI file (17286 Bytes)
• Compressed Postscript file (69712 Bytes)