Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 36 (1995), No. 1, 1-7.

On-line Covering a Box by Cubes

Marek Lassak

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

Abstract. We show that the cube of side s in Euclidean d-space can be on-line covered by every sequence of cubes of sides at most 1 whose total volume is at least a number V (s, d) of the order of magnitude s^{d} with factor 1. MSC 1991: 52C17

1. Introduction

Let C be a set of Euclidean space E^{d}. We say that a sequence C_{1}, C_{2}, … of sets of E^{d} permits a covering of C if there are rigid motions σ_{1}, σ_{2}, … such that C ⊂ ⋃_{i=1}^{∞} σ_{i}C_{i}. A survey of results on covering of convex bodies by sequences of convex bodies is given by Groemer [2]. This paper considers on-line covering methods. The on-line restriction means that we learn C_{i}, where i > 1, only after the motion σ_{i−1} has been provided. At the beginning we are given C_{1}. The on-line restriction for packing and covering is considered in [3–5]. Our aim is an on-line covering of the box

B(s_{1}, …, s_{d}) = { (x_{1}, …, x_{d}); 0 ≤ x_{j} ≤ s_{j}, where j = 1, …, d }

by sequences of d-dimensional cubes of sides at most 1. We present a very efficient method and in Theorem 1 we estimate the total volume of a sequence of cubes which is able to cover the box. The following notation is convenient for a comparison of our methods when our box is a cube of side s, and when s → ∞. If for functions f(s) and g(s) we have lim_{s→∞} f(s)/g(s) = 1, then we write f(s) ∼^{s} g(s) and we say that the functions are asymptotically equal as s → ∞. Our method permits an on-line covering the cube of side s by every sequence of cubes of sides at most 1 whose total volume is at least a number (given in Theorem 2) asymptotically, as s → ∞, equal to s^{d}. So asymptotically, our on-line method is as efficient as the best non-on-line method given in [1].

Research supported in part by Komitet Badań Naukowych (Committee of Scientific Research), grant number 2 2005 92 03

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1994 Heldermann Verlag, Berlin

By ⌊q⌋ we denote the integer part of a real number q, and by ⌈q⌉ we mean the smallest integer which is greater or equal to q.

2. An auxiliary method

Let c > 0. We consider an on-line covering of B(s_{1}, …, s_{d}) by arbitrary sequence Q_{1}, Q_{2}, ... of cubes whose sides are at most c. Let n ∈ {2, 3, …}. We present here a method whose special case, for n = 2 and c = 1 and for the box being the unit cube, is described in [3]. Following [3], we call it the method of current bottom. Let c_{j} be the smallest multiple of c which is greater than or equal to s_{j}, where j = 1, …, d − 1. When we are given Q_{i}, we find the greatest cube K_{i} in it whose side is of length of the form cn^{−r}, where r is a non-negative integer. Let b_{i} ≤ 1 be the greatest number such that every point from B(s_{1}, …, s_{d}) whose last coordinate is smaller than b_{i} has been covered by cubes K_{h} with h < i. Particularly, b_{1} = 0. The set of all points of the box B(s_{1}, …, s_{d}) having the last coordinate b_{i} is called the i-th bottom or the current bottom of the box. Of course, if b_{i} > 0, then the i-th bottom is covered by cubes K_{h} with h < i. A point of the i-th bottom is called surface if no point with the last coordinate greater and with unchanged the other coordinates has been covered by cubes K_{h}, where h < i. We find a rigid motion σ_{i} such that σ_{i}K_{i} contains a surface point of the i-th bottom and that it has the form

{(x_{1}, …, x_{d}); a_{k}cn^{−r} ≤ x_{k} ≤ (a_{k} + 1)cn^{−r} for k = 1, …, d − 1 and b_{i} ≤ x_{d} ≤ b_{i} + cn^{−r}},

where cn^{−r} is the side of K_{i}, and where a_{k} ∈ {0, …, c_{k}n^{r}/c − 1} for k = 1, …, d − 1. Of course, at every moment the current bottom contains surface points. If b_{i} = s_{d} for an index i, then we immediately stop the covering process; the box has been covered by cubes K_{1}, …, K_{i−1}, and so by cubes Q_{1}, …, Q_{i−1}. The method of the current bottom has been described.

Lemma 1. Assume that the box B(s_{1}, …, s_{d}) has been covered by the method of current bottom by a sequence of cubes whose sides are of the form cn^{−r}, where r ∈ {0, 1, …}. The total volume of the cubes used for the covering (up to the moment when we stop the covering) is at most

\frac{n^{d} − 1}{n^{d} − n^{d−1}} (∏_{j=1}^{d−1} c_{j})(s_{d} + c) ,

where c_{j} is the smallest multiple of c being greater than or equal to s_{j}.

Proof. The proof is similar to a part of the proof of Theorem of [3]. Thus we limit the proof here to the remark that Lemma 1 results from the following two facts. Observe that σ_{i}K_{i} covers for the first time a region of the volume at least 1 − (n^{d−1} − 1)/(n^{d} − 1) = (n^{d} − n^{d−1})/(n^{d} − 1) times the own volume (the number (n^{d−1} − 1)/(n^{d} − 1) is the ratio of the sum of the volumes of n^{d} − 1 cubes of each side n^{−r−1}, n^{−r−2}, … to the volume of σ_{i}K_{i} of side n^{−r}). The second fact is that no point out of a box of sides c_{1}, …, c_{d−1}, s_{d} +c is covered when we stop the covering process.

From Lemma 1 for n = 2 and from the fact that the ratio of the volume of Q_{i} to the volume of K_{i} is less than 2^{d} for every i we get Lemma 2.

Lemma 2. Assume that the box B(s_{1}, …, s_{d}) has been covered by the method of current bottom with c = 1 and n = 2 by a sequence of cubes of sides at most 1. The total volume of the cubes used for the covering (up to the moment when we stop the covering) is at most

(2^{d+1} − 2)(∏_{j=1}^{d−1}⌈s_{j}⌉)(s_{d} + 1).

Lemma 2 applied for the d-dimensional cube C_{s}^{d} of side s says that C_{s}^{d} can be on-line covered by the method of current bottom with n = 2 by every sequence of cubes of sides at most 1 whose total volume is a number asymptotically equal to 2^{d+1}s^{d} (as s → ∞).

3. The method of slicing the box

Let p_{2}, …, p_{d−1} be positive integers. For further convenience, let p_{1} = 1. We dissect our box B(s_{1}, …, s_{d}) into subboxes of the form

\{(x_{1}, …, x_{d}); 0 ≤ x_{1} ≤ s_{1} and (k_{j} − 1)\frac{s_{j}}{p_{j}} ≤ x_{j} ≤ k_{j} \frac{s_{j}}{p_{j}} for j = 2, …, d\},

where k_{j} ∈ {1, …, p_{j}} for j = 2, …, d. Let m ≥ 1 and n ≥ 2 be two integers. Every cube whose side is of the length of the form n^{−r−t/m}, where r is a non-negative integer and where t ∈ {0, …, m − 1}, is called a standard cube or an (m, n)-standard cube. The numbers p_{2}, …, p_{d}, m, n are fixed before the covering process starts. The optimal choice for the numbers depends on the values of s_{1}, …, s_{d}. An optimization of the choice for the case when the box is a cube will be discussed in the next part of this paper. We call the below described method the (p_{1}, …, p_{d})-method of (m, n)-standard cubes. The process of the covering consists of two stages. They are called the main stage and the supplementary stage. Here is the main stage: After we learn every cube Q_{i}, we find in it the greatest possible (m, n)-standard cube S_{i}. The ratio of the volumes of Q_{i} and S_{i} is smaller than n^{d/m} for every i. We call n^{d/m} the factor of standardization. Successively we will “slice” the box by creating sets of the form

\{(x_{1}, …, x_{d}); λ ≤ x_{1} ≤ ρ and (k_{j} − 1)\frac{s_{j}}{p_{j}} ≤ x_{j} ≤ k_{j} \frac{s_{j}}{p_{j}} for j = 2, …, d\}, (1)

where k_{j} ∈ {1, …, p_{j}} and where 0 ≤ λ < s_{1}. Moreover, we require that ρ − λ is of the form n^{−t/m}, where t ∈ {0, …, m − 1}. The sets (1) are called slices. We call ρ − λ the thickness of the slice (1). By the left wall (respectively, by the right wall) of this slice we mean the set of the points of this slice whose first coordinate is λ (respectively, ρ). From every new slice we need that λ = 0 or that the left wall of the slice coincides with the right wall of a slice created earlier. Moreover, the interior of every new slice must have empty intersection with the slices created before. The standard cubes of sides of the form n^{−r−t/m} are called proper for the slice whose thickness is of the form n^{−t/m}, and the slice of the thickness n^{−t/m} is called proper for standard boxes of sides n^{−r−t/m}, where t ∈ {0, …, m−1} and r ∈ {1, 2, …}. Every created slice will be successively covered by the method of current bottom by proper standard cubes. The value of c in this method of current bottom is taken to be the thickness n^{−t/m} of this slice. When we have to put Q_{i}, we find S_{i} and we check if there is a proper slice not yet completely covered. If yes, we use S_{i} for covering this slice by the method of current bottom described in the preceding part of the paper. If not, we check if it is possible to create a new proper slice for S_{i}. If possible, we create the proper slice and we use S_{i} for covering it by the method of current bottom. If impossible, we stop the main stage and we pass to the supplementary stage described below. Here is the supplementary stage: We cover every slice which has not been completely covered in the main stage. Every such a slice is a subset of a translation of the box B(1, s_{2}/p_{2}, …, s_{d}/p_{d}). We cover all the translated boxes by the method of current bottom with c = 1 and n = 2.

Theorem 1. The (p_{2}, …, p_{d})-method of (m, n)-standard cubes permits an on-line covering of the box B(s_{1}, …, s_{d}) by arbitrary sequence of d-dimensional cubes of sides at most 1 whose total volume is at least

\frac{n^{d} − 1}{n^{d} − n^{d−1}} n^{d/m} ∏_{j=1}^{d}(s_{j} + p_{j}) + (m − 1)(2^{d+1} − 2)(\frac{s_{d}}{p_{d}} + 1) ∏_{j=2}^{d−1}⌈\frac{s_{j}}{p_{j}} ⌉.  (2)

Proof. We intend to show a slightly stronger statement than promised in the formulation of Theorem 1. Namely, that if B(s_{1}, …, s_{d}) is covered by the (p_{2}, …, p_{d})-method of (m, n)- standard cubes by cubes of sides at most 1, then the total volume of this sequence is at most (2). So assume that B(s_{1}, …, s_{d}) has been covered by our method by a sequence Q_{1}, Q_{2}, … of cubes of sides at most 1. For every totally covered slice in the main stage we apply Lemma 1. Since the factor of standardization is n^{d/m} and since we have used for the covering of every slice only cubes whose standard cubes are proper for this slice, from Lemma 1 we conclude that the total volume of cubes used for the covering of a slice of thickness n^{−t/m} is at most

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

Since the sum of the expressions n^{−t/m} ∏_{j=2}^{d}(s_{j}/p_{j} +1) over all slices is at most ∏_{j=1}^{d}(s_{j} + p_{j}), we see that in the main stage we have used cubes whose total volume is at most

\frac{n^{d} − 1}{n^{d} − n^{d−1}} n^{d/m} ∏_{j=1}^{d}(s_{j} + p_{j}) .  (3)

Now, we estimate the total volume of the cubes used in the supplementary stage. We have at most m − 1 slices for the covering. Each is contained in a translate of the box B(1, s_{2}/p_{2}, …, s_{d}/p_{d}). Applying Lemma 2 we see that the total volume of cubes used in the supplementary stage is at most

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

Since (2) is the sum of (3) and (4), the proof is complete.

4. Optimization of the method of slicing for the on-line covering a cube

Our aim is to discuss the effectiveness of the (p, …, p)-method of (m, n)-standard cubes applied to the cube C_{s}^{d} of side s in E^{d} as our box. Particular question is how to well choose the integers m, n, and p. From Theorem 1 we conclude that C_{s}^{d} can be covered by the (p, …, p)-method of (m, n)- standard cubes by every sequence of cubes of sides at most 1 of the total volume at least

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

A more precise tool than v_{s}^{d}(m, n, p) for the asymptotic comparison of our on-line methods, as s → ∞, is the number

r_{s}^{d}(m, n, p) = v_{s}^{d}(m, n, p) − s^{d}

estimating the reserve over the volume of C_{s}^{d} in the total volume of a sequence of cubes that permits an on-line covering of C_{s}^{d}. Our aim is to find m, n, p for which r_{s}^{d}(m, n, p) is asymptotically, as s → ∞, possibly small. If our m or n is bounded, as s → ∞, then (5) is asymptotically at least a greater than 1 constant times s^{d}, and then the reserve is asymptotically at least a constant times s^{d}. So let us properly choose m and n as functions of s; from (5) we see that we should require n^{d/m} → 1 and m/s → 0 when s → ∞ in order to get the reserve asymptotically smaller than a constant times s^{d}. According to results of many computer experiments for minimization of r_{s}^{d}(m, n, p) for miscellaneous given d and s, we assume that m = dn. Under this assumption, from (5) in which we present n^{1/n} as (n^{1/n} − 1) + 1, and from n(n^{1/n} − 1) ∼^{n} log n we conclude that the asymptotic behaviour of r_{s}^{d}(m, n, p) depends upon the expression

\frac{log n}{n}s^{d} + (d − 1)ps^{d−1} + 2(2^{d} − 1)d\frac{n}{p^{d−1}} s^{d−1} .  (6)

Observe that a good choice for n and p is n = ⌊gs^{d/(d+1)} log^{d/(d+1)} s⌋ and p = = ⌊hs^{1/(d+1)} log^{1/(d+1)} s⌋, where g and h are some constants. Then the maximal order of the three components of (6) is minimized and (6) becomes a constant times s^{d−d/(d+1)} log^{1/(d+1)} s. Applying the first derivative method of finding the smallest value of a real function of two variables we find constants g and h under which (6) is minimized asymptotically, as s → ∞. This choice of g and h means that we take

\begin{aligned}n(d, s) & = ⌊\frac{d}{d + 1}(\frac{2d^{2}}{d + 1}(2^{d} − 1))^{−1/(d+1)}s^{d/(d+1)} log^{d/(d+1)} s⌋ , \\ p(d, s) & = ⌊(\frac{2d^{2}}{d + 1}(2^{d} − 1))^{1/(d+1)}s^{1/(d+1)} log^{1/(d+1)} s⌋ . \end{aligned}

Of course, we take

m(d, s) = dn(d, s) .

Putting m = m(d, s), n = n(d, s), and p = p(d, s) in r_{s}^{d}(m, n, p), and using the facts that n^{1/n} ∼^{n} 1 and n(n^{1/n} − 1) ∼^{n} log n, we get the following theorem.

Theorem 2. Every sequence of cubes of sides at most 1 whose total volume is at least v_{s}^{d}(m(d, s), n(d, s), p(d, s)) permits an on-line covering of the cube C_{s}^{d}. Asymptotically, as s → ∞, this volume is s^{d}. More precisely,

r_{s}^{d}(m(d, s), n(d, s), p(d, s)) ∼^{s} 2(d + 1)(\frac{d^{2}}{d + 1}(1 − 2^{−d}))^{1/(d+1)}s^{d−d/(d+1)} log^{1/(d+1)} s .

Observe that the reserve g_{s}^{d} = (s + 1)^{d} − 1 − s^{d} in the non-on-line method of Groemer (see Theorem 1 of [1]) fulfils g_{s}^{d} ∼^{s} ds^{d−1}. The reserve r_{s}^{d}(m(d, s), n(d, s), p(d, s)) in Theorem 2 is asymptotically smaller than for the best choice of m and n for the simpler case when we do not divide C_{s}^{d} into subboxes. Providing a similar consideration to this presented just before Theorem 2 and assuming that p = 1 we find the following asymptotically good choice for n in order to minimize the reserve:

n′(d, s) = ⌊\frac{1}{2}[d(2^{d} − 1)]^{−1/2}s^{1/2} log^{1/2} s⌋ .

Of course, we take

m′(d, s) = dn′(d, s) .

Substituting these values for m and n and also 1 for p in v_{s}^{d}(m, n, p) and in r_{s}^{d}(m, n, p) and applying (9) and n(n^{1/n} − 1) ∼^{n} log n we obtain

v_{s}^{d}(m′(d, s), n′(d, s), 1) ∼^{s} s^{d} ,

and

r_{s}^{d}(m′(d, s), n′(d, s), 1) ∼^{s} 2[d(2^{d} − 1)]^{1/2}s^{d−1/2} log^{1/2} s .

Particularly, for d = 2 this reserve is asymptotically equal to 2\sqrt{6} s^{3/2} log^{1/2} s while in Theorem 2 the reserve is asymptotically equal to 6s^{4/3} log^{1/3} s. For instance, consider an on-line covering the square of side 1000 by squares of sides at most 1. We have m′(2, 1000) = 32, n′(2, 1000) = 16, and r_{1000}^{2}(32, 16, 1) ≈ 452247. The best choice found by a computer, when we require p = 1, is r_{1000}^{2}(34, 16, 1) ≈ 451419. Much better is to take m(2, 1000) = 240, n(2, 1000) = 120, and p(2, 1000) = 38, which gives r_{1000}^{2}(240, 120, 38) ≈ 129511. The optimal choice found by a computer approach gives r_{1000}^{2}(253, 126, 38) ≈ 129400. So the reserve of 13% is sufficient here while without dividing C_{1000}^{2} into rectangles we need a reserve over 45%.

References

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

[2] Groemer, H.: Coverings and packings by sequences of convex sets, in: Discrete Geometry and Convexity, Annals of the New York Academy of Sciences, vol. 440, 1985, 262–278.

[3] Januszewski, J. and Lassak, M.: On-line covering the unit cube by cubes, Discrete Comput. Geom. 12 (1994), 433–438.

[4] Kuperberg, W.: On-line covering a cube by a sequence of cubes, Discrete Comput. Geom. 12 (1994), 83–90.

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

Received February 28, 1994.