Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 38 (1997), No. 2, 377-384.

On-line Packing Sequences of Segments, Cubes and Boxes

Marek Lassak

Instytut Matematyki i Fizyki ATR, ul. Kaliskiego 7, 85-796 Bydgoszcz, Poland e-mail: lassak@atr.bydgoszcz.pl

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_{s}^{d} 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_{s}^{d} is at most a number of the order of magnitude s^{d−d/(d+2)}. As d → ∞, 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 ≥ 2 is an integer, then every sequence of boxes of edge lengths from the set {q^{0}, q^{−1}, q^{−2} …} and of total volume at most Vol(D) − q[(\frac{q}{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 Vol(D). MSC 1991: 52C17

We say that a sequence C_{1}, C_{2}, … of convex bodies of Euclidean d-space E^{d} can be packed in a set C ⊂ E^{d} if there are rigid motions σ_{i} such that the sets σ_{i}C_{i} , where i = 1, 2, …, have pairwise disjoint interiors and they are subsets of C. A packing process is called translative if only translations are allowed as the rigid motions.

By an on-line packing we mean a packing process in which we are given every C_{i}, where i > 1, only after C_{i−1} has been packed. This restriction means that each set C_{i} must be assigned its place before we learn the next one, and that the placement cannot be changed afterwards.

By a box in E^{d} we understand any set of the form

{(x_{1}, …, x_{d}); r_{j} ≤ x_{j} ≤ s_{j} for j = 1, …, d}.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1997 Heldermann Verlag The number s_{d} − r_{d} is called the height of this box, and the set of points of this box satisfying x_{d} = r_{d} is called the bottom. If r_{1}, …, r_{d}, s_{1}, …, s_{d} are positive integers, then this box is called an integer box. If r_{1} = … = r_{d} = 0, this box is denoted by the symbol B(s_{1}, …, s_{d}). The symbol I_{s}^{d} stands for the d-dimensional cube B(s, …, s).

1. On-line q-adic packing sequences of segments, boxes and cubes

In response to a question of Kuperberg [3], the paper [2] considers the q-adic covering a segment by segments and applies it for proving a result about on-line covering of the unit cube by sequences of cubes of edge lengths at most 1. Here we propose an analogous tool for packing instead of covering.

Let w ≥ 1 and q ≥ 2 be integers. We say that an algorithm of packing the segment [0, w] by a sequence of segments S_{i} of corresponding lengths δ_{i} ∈ {q^{0}, q^{−1}, q^{−2}, …} is q-adic if the rigid motions σ_{i} are restricted so that every segment σ_{i}S_{i} is of the form [c_{i}δ_{i}, (c_{i} + 1)δ_{i}] with c_{i} ∈ {0, … wδ_{i}^{−1} − 1}.

The following on-line q-adic algorithm of packing in the first free fitting segment is very efficient. When we learn S_{i}, we find the smallest a_{i} ∈ {0, …, wδ_{i}^{−1} − 1} such that the interior of the segment [a_{i}δ_{i}, (a_{i} + 1)δ_{i}] remains empty and we pack S_{i} there. If such a segment does not exist, we stop the packing process.

Lemma 1. Let q ≥ 2 and w ≥ 1 be integers. Assume that we are providing the packing of a sequence of segments of lengths from the set {q^{0}, q^{−1}, q^{−2}, …} in the segment [0, w] by the method of the first free fitting segment. If the process of packing is stopped, then the total length of the segments packed up to this moment is greater than w − 1. Every sequence of segments of total length at most w can be packed in [0, w].

Proof. Assume that the process of packing is stopped when we wish to pack a successive segment from the sequence. Let the length of this segment be q^{−n}. Since every segment from the sequence was packed in the first free fitting segment, we have at most q − 1 maximal (by inclusion) free subsegments of [0, w] of every length q^{−n−1}, q^{−n−2}, … when the packing process is stopped. What is more, since a finite number of segments has been packed, the number of those maximal free subsegments is finite. Thus the sum of lengths of those maximal free subsegments is smaller than (q − 1)(q^{−n−1} + q^{−n−2} + …) = q^{−n}. Consequently, the total length of the segments packed up to this moment is greater than w − q^{−n}. We see that the total length of the packed segments is greater than w − 1. This gives the first statement of our lemma. Since the just obtained segment is of length q^{−n}, we see that the total length of segments in our sequence is greater than w. By inversion we obtain the following implication: if the total length of segments is at most w, then the process of packing does not stop after packing only a finite number of segments. This implication is nothing else but the last statement of the lemma.

Let q ≥ 2 be an integer. By a q-adic packing of a sequence of boxes whose edge lengths are from the set {q^{0}, q^{−1}, q^{−2}, …} we mean a packing in which every box B(y_{1}, …, y_{d}) from the sequence is moved so that the following two conditions are satisfied: (a) after packing, the box is a translation of B(v_{1}, …, v_{d}), where v_{1}, …, v_{d} is a permutation of y_{1}, …, y_{d}, (b) for every j ∈ {1, …, d}, the projection of B(v_{1}, …, v_{d}) on the j-th coordinate axis is a segment whose both endpoints are multiples of v_{j}.

We will pack the boxes in the union of a number of unit cubes. This is convenient for applications. Assume for convenience that this union of w cubes has the form

G_{w}^{d} = {(x_{1}, …, x_{d}); 0 ≤ x_{j} ≤ 1 for j = 1, …, d − 1, and 0 ≤ x_{d} ≤ w}.

Below we describe an on-line translative q-adic method of strips for q-adic packing of sequences of boxes. We apply induction in respect to the dimension.

If d = 1, we use the algorithm of the first free fitting segment.

Assume that the method is described in E^{d−1}, where d ≥ 2. We give the description for E^{d}. For every r ∈ {0, 1, 2, …} we dissect G_{w}^{d} into wq^{r} horizontal strips of height q^{−r}.

Every box is packed in a strip of heigth equal to the heigth of this box. Every strip properly containing such a strip or properly contained in such a strip is closed for further packing. When we are given a box B(y_{1}, …, y_{d}) from our sequence, we take into account only the strips of height y_{d} which are not yet closed for packing. We consider the bottoms of those strips and the bottoms of boxes of height y_{d} that were earlier packed in those strips. We apply the (d − 1)-dimensional procedure to those bottoms in order to find the proper position for packing the bottom of B(y_{1}, …, y_{d}). We pack B(y_{1}, …, y_{d}) so that its bottom moves to this position.

Lemma 2. Every sequence of boxes of edge lengths from the set {q^{0}, q^{−1}, q^{−2}, …} and of total volume at most w − q[(\frac{q}{q−1})^{d−1} − 1] can be packed in w unit cubes by the method of strips.

Proof (by induction). Put z^{d}(q) = q[(\frac{q}{q−1})^{d−1} − 1]. If d = 1, then Lemma 2 holds true by Lemma 1. Assume that our lemma is true in E^{d−1}. Assume that the d-dimensional process of packing is stopped at a moment when we wish to pack a successive box from the sequence. Let the height of this box be q^{−b}. Denote by γ(a) the number of open strips of height q^{−a}, where a = 0, 1, 2, . . .. Since every box was packed in the ”lowest” nonclosed strip, by the inductive hypothesis we conclude that the total (d − 1)-dimensional volume of the bases of the given boxes of height q^{−b} (including the last box that cannot be packed) is greater than γ(b) − z^{d−1}(q). Thus the total volume of those boxes is greater than q^{−b}(γ(b)−z^{d−1}(q)). Similarly, we conclude that if a ≠ b, then the total volume of the packed boxes of height q^{−a} is greater than q^{−a}(γ(a) − z^{d−1}(q) − 1). We see that the total volume of all given boxes (including the last box that cannot be packed) is greater than ∑_{a=0}^{∞}[q^{−a}(γ(a) − z^{d−1}(q) − 1)] + q^{−b} = ∑_{a=0}^{∞} γ(a)q^{−a} − (z^{d−1}(q) + 1) ∑_{a=0}^{∞} q^{−a} + q^{−b} = w − q^{−b} − (z^{d−1}(q) + 1)\frac{q}{q−1} + q^{−b} = w − z^{d}(q). A contradiction.

For the method of strips the estimate given in Lemma 2 is sharp. For d = 2 this follows from the example of the finite sequence of boxes whose first t + 1 boxes are B(q^{−t}, q^{0}), B(q^{−t}, q^{−1}), …, B(q^{−t}, q^{−t}), and the remaining wq^{t} − (q^{1} + … + q^{t}) boxes are of the form B(q^{0}, q^{−t}). This sequence cannot be packed even though its total area is smaller than w − \frac{q}{q−1} + 2q^{−t} \frac{q}{q−1}. This value tends to w − \frac{q}{q−1} = w − q[\frac{q}{q−1} − 1] as t tends to ∞. A construction of an analogous example in d-space is left to the reader. The author does not know if the estimate of Lemma 2 can be improved by an application of a different on-line translative q-adic packing method. The question of possible improvements when we drop one or both the first two of those assumptions is open.

Let u > 0. Cubes of edge lengths of the form u2^{−k}, where k ∈ {0, 1, 2, …}, are called u-standard. We will apply the 2^{d}-adic packing a segment by segments in order to describe a method of on-line packing of sequences of u-standard cubes in a number of cubes of edge length u, called u-stores. We denote those u-stores by A_{1}, …, A_{w} and we assume that they have pairwise disjoint interiors. We can represent every u-store A_{g} as τ_{g}(I_{u}^{d}), where τ_{g} is a translation. Let ϕ_{k} be a bijection between the family of segments of the form Y_{k}(h) = [h2^{−dk}, (h + 1)2^{−dk}], where h = 0, …, w2^{dk} − 1, and the family of u-standard cubes

τ_{g}{(x_{1}, …, x_{d}); uh_{j}2^{−k} ≤ x_{j} ≤ u(h_{j} + 1)2^{−k} for j = 1, …, d},

where h_{1}, …, h_{d} ∈ {0, …, 2^{k} − 1} and g ∈ {1, …, w}. Let ϕ_{k} be given for k = 0, 1, 2, … such that the following two conditions hold:

(i) ϕ_{0}([h, h + 1]) = A_{h+1} for h = 0, …, w − 1, (ii) if Y_{m}(a) ⊂ Y_{n}(b), then ϕ_{m}(Y_{m}(a)) ⊂ ϕ_{n}(Y_{n}(b)). We describe the packing of a sequence of u-standard cubes applying a simultaneous

auxiliary process of 2^{d}-adic packing a sequence of segments in the segment [0, w]. Assume that we are given a u-standard cube K from our sequence. If its edge length is u2^{−k}, then we pack a segment S of length 2^{−dk} in [0, w] according to the 2^{d}-adic method of the first free fitting segment. Let σS denote the position of S after it is packed. Then ϕ_{k}(σS) is the rigth place in A_{1} ∪ … ∪ A_{w} for putting our cube K. We call this approach packing in the first free fitting subcube.

It is clear that the method described above is on-line, translative and q-adic.

Since a cube of volume u^{d}2^{−dk} always corresponds to a segment of length 2^{−dk} in our bijection, Lemma 1 implies the following statement.

Lemma 3. Let A_{1}, …, A_{w} be u-stores with pairwise disjoint interiors. Assume that we are packing a sequence of u-standard cubes in A_{1} ∪ … ∪ A_{w} by the method of the first free fitting subcube. If the process of packing is stopped, then the total volume of the cubes packed up to this moment is greater than (w − 1)u^{d}. Every sequence of u-standard cubes of total volume at most wu^{d} can be packed in A_{1} ∪ … ∪ A_{w}.

Lemma 3 remains valid for an analogous method with an arbitrary integer q ≥ 2 instead of 2. If u = 1 in Lemma 3, we get the 2-adic packing of cubes.

We need the method of the first free fitting subcube for the description of the algorithm presented in Part 2. Lemma 3 is needed for the proof of Theorem 2.

We apply Lemma 2, and Lemma 3 with u = 1 for the on-line q-adic packing of sequences of cubes and boxes in an integer box D. For this purpose we present D as the union of unit cubes. We obtain the following theorem.

Theorem 1. Let D be an integer box and let q ≥ 2 be an integer. An arbitrary sequence of boxes of edge lengths from the set {q^{0}, q^{−1}, q^{−2} …} whose total volume is at most Vol(D)−q[(\frac{q}{q−1})^{d−1} −1] permits a translative on-line q-adic packing in D. If all the boxes are assumed to be cubes, the packing is possible when the total volume is at most Vol(D).

2. On-line packing of sequences of cubes in a box

Below we present a method of packing sequences of cubes of edge lengths at most 1 in the box B(s_{1}, …, s_{d}), where s_{1} ≥ 1, …, s_{d} ≥ 1. Let p_{1} ≥ s_{1}, …, p_{d} ≥ s_{d} be integers. Using p_{j} − 1 hyperplanes perpendicular to the j-th coordinate axis, where j = 1, …, d, we divide the box into ∏_{j=1}^{d} p_{j} congruent subboxes.

Let m be a positive integer. The number 2^{−d/m} is called the factor of standardization. We define the family of standard cubes as the union of the families of 2^{−t/m}-standard cubes for t = 0, …, m − 1. Every cube from our sequence of cubes is enlarged to the smallest possible standard cube. The volume increases less than 2^{d/m} times. It remains to explain how to pack the corresponding sequence of standard cubes.

For every t ∈ {0, …, m − 1}, the subsequence of all 2^{−t/m}-standard cubes of the sequence of standard cubes is packed in a number of 2^{−t/m}-stores. We apply here the method of the first free fitting subcube with u = 2^{−t/m}. For every t ∈ {0, …, m−1}, the set of the 2^{−t/m}-stores is successively constructed during the packing process. We open a new portion of 2^{−t/m}-stores each time when we obtain a 2^{−t/m}-standard cube K, and if in the existing 2^{−t/m}-stores there is not enough empty room for packing K according to the method of the first free fitting subcube. In particular, we do so when no 2^{−t/m}-store has been opened yet. A new portion of 2^{−t/m}-stores is opened in any subbox not used yet for storing cubes. We find there a greatest possible box of the form τ(B(z_{1}2^{−t/m}, …, z_{d}2^{−t/m})), where z_{1}, …, z_{d} are positive integers, and where τ is a translation. We dissect this box into ∏_{j=1}^{d} z_{j} cubes of edge length 2^{−t/m} whose interiors are pairwise disjoint. They are the required new 2^{−t/m}-stores. We stop the packing process if a succeding cube cannot be packed according to the described method, i.e. if no new free subbox exists when we wish to open a new portion of 2^{−t/m}-stores.

Theorem 2. Every sequence of cubes of edge lengths at most 1 and total volume at most

2^{− \frac{d}{m}} (∏_{j=1}^{d} p_{j} − m + 1) ∏_{j=1}^{d}(\frac{s_{j}}{p_{j}} − 1)  (1)

can be on-line packed in the box B(s_{1}, …, s_{d}) by the method of dividing the box into ∏_{j=1}^{d} p_{j} congruent subboxes and by using m types of stores.

Proof. Assume that we cannot pack a successive cube from the sequence. Let the smallest standard cube containing this cube be a 2^{−n/m}-standard cube, where n ∈ {0, …, m − 1}.

Let ξ(t) denote the number of the subboxes into which we have packed the 2^{−t/m}- standard cubes during the whole packing process. Let t ∈ {0, …, m − 1}. Putting u = 2^{−t/m} and w = ξ(t) ∏_{j=1}^{d} z_{j} in Lemma 3, we see that the volume of the packed 2^{−t/m}- standard cubes is greater than (ξ(t) − 1) ∏_{j=1}^{d}(z_{j}2^{−t/m}). Since s_{j}/p_{j} − 1 < z_{j}2^{−n/m} for j = 1, …, d, this volume is greater than (ξ(t) − 1) ∏_{j=1}^{d}(s_{j}/p_{j} − 1). Taking all such volumes for t = 0, …, m − 1 and adding the volume of the cube that cannot be packed we obtain total volume greater than (∏_{j=1}^{d} p_{j} − m + 1) ∏_{j=1}^{d}(s_{j}/p_{j} − 1). Since the factor of standardization is 2^{−d/m}, the total volume of the given cubes (including the last box that cannot be packed) is greater than (1). A contradiction.

Theorem 2 can be reformulated as follows: if the packing process is stopped, then the total volume of the given cubes is greater than the quantity in (1).

3. On-line packing sequences of cubes in a cube

We intend to discuss the efficiency of the method presented in the preceding part in the special case when B(s_{1}, …, s_{d}) is the cube I_{s}^{d} divided into p^{d} subcubes. Our aim is to choose p and m in order to maximize, asymptotically, as s → ∞, the total volume of cubes of edge lengths at most 1 that can be packed in I_{s}^{d}.

If for functions f(s) and g(s) we have lim_{s→∞} f(s)/g(s) = 1, we write f(s) ∼^{s} g(s). If a packing method ensures a packing of I_{s}^{d} by every sequence of boxes of edge lengths at most 1 and of total volume v_{s}^{d} such that v_{s}^{d} ∼^{s} s^{d}, as s → ∞, then we take into account the number u_{s}^{d} = s^{d} − v_{s}^{d} which estimates the volume which remains unfilled in I_{s}^{d}. We get a tool for comparing the efficiency of the packing methods which fulfil v_{s}^{d} ∼^{s} s^{d}.

The formula from Theorem 2 has now the following simpler form

v_{s}^{d}(m, p) = 2^{− \frac{d}{m}} (p^{d} − m + 1)(\frac{s}{p} − 1)^{d} = 2^{− \frac{d}{m}} (1 − \frac{m − 1}{p^{d}})(s − p)^{d}.

If we properly choose p and m with regard to d and s, then v_{s}^{d}(m, p) is of the order of magnitude s^{d} with factor 1; for instance, v_{s}^{d}(⌊\sqrt{s}⌋, ⌊\sqrt{s}⌋) ∼^{s} s^{d}. Observe that if p or m are bounded from above and if s → ∞, then v_{s}^{d}(m, p) cannot be of the order of magnitude s^{d} with factor 1. Thus we will assume that m → ∞ and p → ∞ provided s → ∞. Hence we do not make our consideration narrower assuming that m ≥ (log2)ed. This assumption means that m can be presented as (log2)dk/log k, where k ≥ e. Obviously, 2^{−d/m} = k^{−1/k}. The volume of the unfilled space in I_{s}^{d} is at most u_{s}^{d}(m, p) = s^{d} − v_{s}^{d}(m, p). We have

u_{s}^{d}(m, p) = s^{d} − k^{−1/k}[1 − \frac{1}{p^{d}} (\frac{(log 2)dk}{log k} − 1)](s − p)^{d}.  (2)

If we write k^{−1/k} as 1 − (1 − k^{−1/k}) and if we take into account that k(1 − k^{−1/k}) ∼^{k} log k, then by exchanging k^{−1/k} for 1−(log k)/k in (2) we observe that the asymptotic behaviour of u_{s}^{d}(m, p), as s → ∞, depends upon the expression

[\frac{log k}{k} + (log 2)d\frac{1}{p^{d}} \frac{k}{log k} ]s^{d} + dps^{d−1}.  (3)

If we take p = ⌊λs^{2/(d+2)}⌋ and k = μd^{1/2}p^{d/2}log p, where λ and μ are some constants, then the maximal order of magnitude of the components of (3) is minimized and (3) becomes a constant times s^{d−d/(d+2)}. We omit here a tedious calculation for finding the constants λ and μ which mimimize (3) asymptotically as s → ∞. They are λ = [(log 2)d]^{1/(d+2)} and μ = \frac{1}{2} \sqrt{d/(log 2)}. Substituting p and k with those values of λ and μ in (3) we conclude that u_{s}^{d} ∼^{s} cs^{d−d/(d+2)}, where c = (d + 2)(d log 2)^{1/(d+2)}. Clearly, k determines m = ⌊d(log 2)k/log k⌋.

From the above considerations we obtain the following theorem.

Theorem 3. Every sequence of cubes of edge lengths at most 1 whose total volume is at most 2^{−d/m}(p^{d} − m + 1)(\frac{s}{p} − 1)^{d} can be on-line packed in the cube I_{s}^{d} by the method of dividing I_{s}^{d} into p^{d} congruent subcubes and by using m types of stores. If we properly choose m and p with regard to d and s, then this estimate is of the order of magnitude s^{d} with factor 1, and u_{s}^{d} ∼^{s} cs^{d−d/(d+2)}, where c = (d + 2)(d log 2)^{1/(d+2)}.

Corollary. The above method of packing a sequence of cubes of edge lengths at most 1 in I_{s}^{d} guarantees that if a succeding cube cannot be packed, then the volume of the unfilled part of I_{s}^{d} is at most a number of the order of magnitude s^{d−d/(d+2)} with factor (d + 2)(d log 2)^{1/(d+2)}.

We have (d + 2)(d log 2)^{1/(d+2)} ∼^{d} d and s^{d−d/(d+2)} ∼^{d} s^{d−1}. Thus, if s → ∞ and d →

∞, then the estimate of the volume u_{s}^{d} that remains unfilled when applying Theorem 3 approaches the analogous estimate ds^{d−1} in the off-line packing method of Groemer [1]. The order of magnitude of u_{s}^{d} in Theorem 3 is smaller than the corresponding order of magnitude s^{d−d/(2d−1)} in the method of [4] for d > 3, and they are equal for d = 3.

4. On-line packing sequences of boxes

Natural questions are if the method considered in Parts 2 and 3 can be generalized for packing boxes instead of cubes, and if the efficiency of such a generalized method is again better than the efficiency of the method from [4]. The answer to the first question is positive. But the order of magnitude of the unfilled space in I_{s}^{d} appears to be sligthly higher than that from [4]. Nevertheless, for the sake of the completness of the paper, we shortly describe this algorithm.

Let u_{1}, … u_{d} be positive reals. Boxes of the form B(u_{1}2^{−r_{1}}, …, u_{d}2^{−r_{d}}), where r_{1}, …, r_{d} ∈ {0, 1, 2, …}, are called (u_{1}, …, u_{d})-standard. There is a homothety χ such that χ(B(2^{−r_{1}}, …, 2^{−r_{d}})) = B(u_{1}2^{−r_{1}}, …, u_{d}2^{−r_{d}}) for every r_{1}, …, r_{d} ∈ {0, 1, 2, …}. According to the above homothety and to the method of strips, we define an auxiliary algorithm for on-line packing sequences of (u_{1}, …, u_{d})-standard boxes in a number of translations of B(u_{1}, …, u_{d}) (with pairwise disjoint interiors) called (u_{1}, …, u_{d})-stores. Applying Lemma 2 with q = 2 we obtain the following lemma analogous to Lemma 3.

Lemma 4. Let A_{1}, …, A_{w} be (u_{1}, …, u_{d})-stores with pairwise disjoint interiors. If the process of packing of a sequence of (u_{1}, …, u_{d})-standard boxes in A_{1} ∪ … ∪ A_{w} by the above auxiliary algorithm is stopped, then the total volume of the packed boxes is greater than (w−2^{d}+1) ∏_{j=1}^{d} u_{j}. Every sequence of (u_{1}, …, u_{d})-standard boxes whose total volume is at most (w − 2^{d} + 2) ∏_{j=1}^{d} u_{j} can be packed in A_{1} ∪ … ∪ A_{w}.

Here is the promised generalized method of packing sequences of boxes of edge lengths at most 1 in B(s_{1}, …, s_{d}). By standard boxes we mean the (2^{−t_{1}/m}, …, 2^{−t_{d}/m})-standard boxes, where t_{1}, …, t_{d} ∈ {0, …, m − 1}. Every box is packed together with the smallest possible standard box containing it. The volume enlargement factor is smaller than 2^{d/m}. For every t_{1}, …, t_{d} ∈ {0, …, m − 1}, we pack the subsequence of all (2^{−t_{1}/m}, …, 2^{−t_{d}/m})- standard boxes in a number of (2^{−t_{1}/m}, …, 2^{−t_{d}/m})-stores. We apply here the auxiliary algorithm. For every t_{1}, …, t_{d} ∈ {0, …, m − 1}, the (2^{−t_{1}/m}, …, 2^{−t_{d}/m})-stores are constructed during the packing process. We open a new portion of them each time when we obtain a (2^{−t_{1}/m}, …, 2^{−t_{d}/m})-standard box which cannot be packed in the existing (2^{−t_{1}/m}, …, 2^{−t_{d}/m})-stores. We open this new portion of (2^{−t_{1}/m}, …, 2^{−t_{d}/m})-stores in a new subbox. We find there a greatest box of the form τ(B(z_{1}2^{−t_{1}/m}, …, z_{d}2^{−t_{d}/m})), where z_{1}, …, z_{d} are positive integers, and where τ is a translation. We dissect this box into ∏_{j=1}^{d} z_{j} (2^{−t_{1}/m}, …, 2^{−t_{d}/m})-stores. The packing process is stopped if a box cannot be packed by the above rules.

Proposition. We can pack arbitrary sequence of boxes of edge lengths at most 1 whose total volume is at most

2^{− \frac{d}{m}} [(∏_{j=1}^{d} p_{j} − m^{d} + 1) ∏_{j=1}^{d}(\frac{s_{j}}{p_{j}} − 1) − (2^{d} − 2)m^{d}]

in the box B(s_{1}, …, s_{d}) by the method of dividing this box into ∏_{j=1}^{d} p_{j} congruent subboxes and by using m^{d} types of stores. In the case of packing in the cube I_{s}^{d} divided into p^{d} congruent subcubes, we can choose m and p so that this estimate is of the order of magnitude s^{d} with factor 1 and that u_{s}^{d} ∼^{s} cs^{d−d/(2d+1)}, where c is a constant.

The proof is analogous to the proofs of Theorems 2 and 3. Instead of Lemma 3, this time we apply Lemma 4.

References

[1] Groemer, H.: Covering and packing properties of bounded sequences of convex sets. Mathematika 29 (1982), 18–31.

[2] Januszewski, J.; Lassak, M.; Rote, G.; Woeginger, G.: On-line q-adic covering by the method of the n-th segment and its application to on-line covering by cubes. Beiträge Algebra Geom. 37 (1996), 51–65.

[3] Kuperberg, W.: Problem 74: Ein Intervallüberdeckungsspiel. Math. Semesterber. 41 (1994), 207–210.

[4] Lassak, M.; Zhang, J.: An on-line potato-sack theorem. Discrete Comput. Geom. 6 (1991), 1–7.

Received June 28, 1996; revised version November 6, 1996