Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 43 (2002), No. 2, 537-549.

On-line Algorithms for the q-adic Covering of the Unit Interval and for Covering a Cube by Cubes

Marek Lassak^{∗}

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

Abstract. We present efficient algorithms for the on-line q-adic covering of the unit interval by sequences of segments. The basic method guarantees covering provided the total length of segments is at least 1 + 2 · \frac{1}{q} − \frac{1}{q^{3}} . Other algorithms improve this estimate for q ≥ 6. The unit d-dimensional cube can be on-line covered by an arbitrary sequence of cubes whose total volume is at least 2^{d} + \frac{5}{3} + \frac{5}{3} · 2^{−d}. MSC 2000: 52C17

We say that a sequence Q_{1}, Q_{2}, … of subsets of Euclidean space E^{d} permits a covering of a set C ⊂ E^{d} if there exist rigid motions τ_{1}, τ_{2}, … such that C is contained in the union of sets τ_{1}Q_{1}, τ_{2}Q_{2}, . . .. Many questions arise about efficient covering algorithms. In the on-line version of this problem, at the beginning we are given the first set Q_{1} but then we learn every succeeding set Q_{i} from the sequence only after the preceding set Q_{i−1} is used for the covering. The reader can find more information about on-line covering algorithms in the survey articles [1] and [7]. We prove that an arbitrary sequence of cubes whose total volume is at least 2^{d} + \frac{5}{3} + \frac{5}{3} · 2^{−d} is able to cover on-line the unit d-dimensional cube. This is very close to the best off-line estimate of 2^{d} − 1 (see [2]).

The closed interval with end-points x and y, where x < y, is denoted by [x, y]. The symbol (x, y) denotes the corresponding open interval.

538 M. Lassak: On-line Algorithms for the q-adic Covering …

Recall the on-line q-adic covering problem (see [6]). Let q ≥ 2 be an integer. Find an efficient algorithm for the on-line covering of the interval [0, 1] by a sequence of closed segments S_{i} of lengths δ_{i}, where δ_{i} ∈ {q^{−1}, q^{−2}, …}, and where every segment τ_{i}S_{i} is of the form [c_{i}δ_{i}, (c_{i} + 1)δ_{i}] with c_{i} ∈ {0, …, δ_{i}^{−1} − 1} for i = 1, 2, . . ..

∗ Research supported by Deutsche Forschungsgemeinschaft and provided at Freie Universität Berlin, grant Be 142/62-1 0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}2002 Heldermann Verlag

We present an algorithm which is a substantial modification of the algorithm from [3]. We improve the assumption about the total length of a sequence of segments which allows a covering from a little less than 1 + 3 · \frac{1}{q} to a little less than 1 + 2 · \frac{1}{q}. Next we propose a more sophisticated algorithm which lowers the above estimate to a little over 1 + \frac{5}{3} · \frac{1}{q}. We also show how to decrease the factor \frac{5}{3} ≈ 1.667 arbitrarily close to \frac{1}{2}(1 + \sqrt{5}) ≈ 1.618. A natural question is about more efficient algorithms.

An open problem is about a non-trivial lower estimate. The only known such estimate is \frac{4}{3} = 1 + \frac{2}{3} · \frac{1}{2} for q = 2 (see [4]).

Here is our basic algorithm. At every moment of the covering process we take into account the greatest number b ∈ [0, 1] such that the whole interval [0, b] is covered. We call b the current bottom. When a segment S, say of length q^{−r}, is given to us, we find the greatest integer a such that aq^{−r} ≤ b. If the interval [(a + h − 1)q^{−r}, (a + h)q^{−r}], where h ∈ {1, 2, …}, is a subset of [0, 1], then we call it the h-th interval. We place S on the first not totally covered h-th interval of length q^{−r} selected in the following order: the (q + 1)-th interval, then the q-th interval and so on up to the 2-nd interval, next the (q + 2)-nd interval and the successive intervals up to the 2q-th interval, and finally the 1-st interval. We end the covering process when the whole interval [0, 1] is covered.

It is natural to call this algorithm the (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm. In particular, for q = 2 we get the (3, 2, 4, 1)-algorithm that tries to place every segment by checking successively the 3-rd, the 2-nd, the 4-th and the 1-st interval of length 2^{−r}.

For the convenience of the reader, who possibly will compare the considerations, the proof of Theorem 1 is organized similarly as the proof of Theorem 1 in [3]. We use analogous notation to that in [3]. In particular, we have three analogous lemmas. Here is a lemma similar to Lemma 1 in [3]. Also the proof is similar, hence we omit it.

Lemma 1. Let p < 1 be a positive multiple of q^{−w}. Assume that the interval [0, p] is not completely covered yet by the (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm. For j ≥ 0 denote by ν_{j} the number of segments of length q^{−w−j} placed to the right of p. Assume that ν_{0} ≥ q − 1, …, ν_{ℓ} ≥ q − 1 for some ℓ ≥ 0. Then there is at most one number z ∈ {0, …, l} such that a segment of length q^{−w−z} used for the covering contains p. In such a case we have ν_{j} ≤ q − 1 for each j ∈ {0, …, z − 1}, we have q ≤ ν_{z} ≤ 2q − 1, we have q − 1 ≤ ν_{j} ≤ 2q − 2 for every j > z, and the interval [p, p + q^{−w+1}] is completely covered.

For every integer i > 1, we denote by b_{i} the position of the current bottom immediately after putting the first i − 1 segments from our sequence. Moreover, let b_{1} = 0.

Lemma 2. Assume that we apply the (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm and that b_{i} < b_{i+1} < 1. Let Δb = b_{i+1} − b_{i} and let Δl be the total length of those among the first i placed segments that have non-empty intersection with (b_{i}, b_{i+1}). Then

Δl < (1 + \frac{1}{q} + \frac{1}{q^{2}} )Δb.

Proof. Let w mean the smallest positive integer such that a segment of length q^{−w} has been used for the covering of the interval (b_{i}, b_{i+1}). Of course,

q^{−w} < Δb ≤ 2q · q^{−w}.

We have Δb = λ_{0}q^{−w}, where λ_{0} ∈ {2, …, 2q} or

Δb = λ_{0}q^{−w} + λ_{k}q^{−w−k} + … + λ_{m}q^{−w−m},

where λ_{0} ∈ {1, …, 2q}, 1 ≤ k ≤ m and λ_{k}, …, λ_{m} ∈ {0, …, q − 1} with λ_{k} ≥ 1, λ_{m} ≥ 1. Clearly, if λ_{0} ≥ 2, then b_{i+1} is a multiple of q^{−w}. By the last segment we mean the segment whose placement completes the covering of the interval (b_{i}, b_{i+1}). Denote by q^{−t} the length of the last segment put on (b_{i}, b_{i+1}) and by μ_{j} the number of segments of length q^{−w−j}, distinct from the last segment and used for the covering of the interval (b_{i}, b_{i+1}). We have 0 ≤ μ_{j} ≤ 2q. Of course, Δl = q^{−t} + ∑_{j=0}^{∞} μ_{j}q^{−w−j}.

In Cases 2 and 3 we will consider the smallest multiple p of q^{−w} such that the interval [0, p] is not totally covered after putting all segments but the last one. Observe that the last segment is placed so that p becomes its right end-point. Since λ_{k}q^{−w−k} +…+λ_{m}q^{−w−m} < q^{−w−k+1}, all segments (except the last one) of lengths between q^{−w−k+1} and q^{−w} used for the covering of (b_{i}, b_{i+1}) are placed to the right of p. Figures 1–7 below show some extreme situations in the considered cases and subcases. We present the order in which the segments are put on the interval [b_{i}, b_{i+1}] by showing them level by level. A lower level means that a segment is placed later. In order to focus our attention, we always take q = 3. The figures show only segments of length at least q^{−w−2} since shorter segments cannot be well drawn here. For a clear presentation of the worst situation to the right of p, in Figures 4–7 we have 0 < p − b_{i} < q^{−w−2} despite in general 0 < p − b_{i} < q^{−w}.

Case 1, when Δb = s·q^{−w} for s ∈ \{2, …, 2q\}. We will show that Δl < (1+ \frac{1}{q})Δb holds true in Case 1. This inequality is stronger than the inequality announced in the formulation of Lemma 2. Observe that b_{i} and b_{i+1} are multiples of q^{−w}. Subcase 1.1, when s = 2q. We have Δl < q^{−t} + (2q − 1)q^{−w} + (2q − 2)q^{−w−1} + (2q − 2)q^{−w−2} +… ≤ 2q^{−w} +(2q−2) ∑_{j=w+1}^{∞} q^{−j} = (2q−2)\frac{q}{q−1}2q^{−w} +2q·q^{−w} = (2q+2)q^{−w} = (1 + \frac{1}{q})Δb. In this evaluation we consider at most 2q − 2 segments of each of the lengths q^{−w−1}, q^{−w−2}, …, despite that it may happen that we place 2q − 1 segments of a specific length q^{−w−c}, where c ∈ {1, 2, …}. In such a case we have at least one less (than in the above evaluation) segment of length q^{−w−c+1} and thus the estimate still holds true.

Fig. 1. A sequence of maximum total length in Subcase 1.1 Subcase 1.2, when s ∈ {q + 1, …, 2q − 1}. This time the last segment has length at most q^{−w−1}. We have Δl < q^{−t} + (s − 1)q^{−w} + (2q − 2) ∑_{j=w+1}^{∞} q^{−j} ≤ q^{−w−1} + (s − 1)q^{−w} + (2q − 2)\frac{q}{q−1}q^{−w−1} = (s + \frac{q+1}{q})q^{−w} ≤ (s + \frac{s}{q})q^{−w} ≤ (1 + \frac{1}{q})Δb. We take here into account a similar remark about the coefficients 2q − 2 like in the previous subcase.

Fig. 2. A sequence of maximum total length in Subcase 1.2

Subcase 1.3, when s ∈ {2, …, q}. The situation of this subcase occurs when a few segments of length q^{−w} are placed without causing an immediate increase of the current bottom, and later the current bottom grows close to those segments thanks to placing sufficiently many shorter segments. Again the last segment has length at most q^{−w−1} but fewer segments of length q^{−w−1} can be placed to the left of b_{i} + q^{−w}. We obtain Δl < q^{−t} + (s − 1)q^{−w} + (q − 1)q^{−w−1} + (2q − 2) ∑_{j=w+2}^{∞} q^{−j} ≤ q^{−w−1} + s · q^{−w} − q^{−w−1} + (2q − 2)\frac{q}{q−1}q^{−w−2} = (s + \frac{2}{q})q^{−w} ≤ (s + \frac{s}{q})q^{−w} ≤ (1 + \frac{1}{q})Δb. And again we have in mind a similar remark about the coefficients 2q − 2 as in Subcase 1.1.

Fig. 3. A sequence of maximum total length in Subcase 1.3

Case 2, when q · q^{−w} < Δb < 2q · q^{−w} and when Δb is not a multiple of q^{−w}. Of course, q ≤ λ_{0} ≤ 2q − 1 and μ_{0} ≥ q − 1.

Subcase 2.1, when μ_{1} ≥ q − 1, …, μ_{k−1} ≥ q − 1. Assume first that there is a z ∈ {1, …, k − 1} such that a placed segment of length q^{−w−z}, distinct from the last segment, contains p. Lemma 1 implies that the sum of the lengths of segments (distinct from the last segment) of lengths between q^{−w−k+1} and q^{−w} put on (b_{i}, b_{i+1}) is at most (λ_{0} − 1)q^{−w} + (2q − 2) ∑_{j=w+1}^{w+z−1} q^{−j} + (2q − 1)q^{−w−z} + (q − 1) ∑_{j=w+z+1}^{w+k−1} q^{−j} = (λ_{0} + 1)q^{−w} − q^{−w−k+1} (we take z = 1 in Fig. 4). We applied Lemma 1 since segments of length at most q^{−w−k+1} are placed to the right of p. It may also happen that μ_{0} = λ_{0} and that [p, p + q^{−w}] is covered by a segment of length q^{−w} placed “a long time before” the current bottom has arrived up to our present b_{i} (thus [p + q^{−w}, p + 2q^{−w}] is covered by a segment of length q^{−w} later than [p, p + q^{−w}]). Then the total length is at most λ_{0}q^{−w} + (q − 1)q^{−w−1}.

Fig. 4. A sequence of maximum total length in the first part of Subcase 2.1

Now assume that p is not in the segments of lengths q^{−w−1}, …, q^{−w−k+1} distinct from the last segment used for the covering. The sum of the lengths of the considered segments is at most λ_{0}q^{−w} + (q − 1) ∑_{j=w+1}^{w+k−1} q^{−j} = (λ_{0} + 1)q^{−w} − q^{−w−k+1}.

Fig. 5. A sequence of maximum total length in the second part of Subcase 2.1

We see that always the sum of lengths of the segments distinct from the last segment put on (b_{i}, b_{i+1}), whose lengths are between q^{−w−k+1} and q^{−w}, is at most

(λ_{0} + 1)q^{−w} − q^{−w−k+1}.  (1)

Now we estimate the total length of segments of length at most q^{−w−k} distinct from the last segment put on (b_{i}, b_{i+1}). The total length of them is less than ∑_{j=w+k}^{w+m−1}(λ_{j−w} + q − 1)q^{−j} + (λ_{m} + q − 2)q^{−w−m} + ∑_{j=w+m+1}^{∞}(2q − 2)q^{−j} = ∑_{j=w+k}^{w+m} λ_{j−w}q^{−j} + (q − 1) ∑_{j=w+k}^{w+m−1} q^{−j} + (q − 2)q^{−w−m} + (2q − 2) ∑_{j=w+m+1}^{∞} q^{−j}, which is less than

∑_{j=w+k}^{w+m} λ_{j−w}q^{−j} + q^{−w−k+1}.  (2)

In the above calculation we see components (λ_{j} + q − 1)q^{−j} despite that sometimes up to 2q − 1 segments of length q^{−j} can be put on (b_{i}, b_{i+1}) during the covering process. But then the estimate (2) holds true as well. Just if between λ_{j} + q and 2q − 1 segments of a specific length q^{−j}, where j ∈ {w + k + 1, …, w + m − 1}, are used for the covering, then one less segment of length q^{−j+1} can be placed there because of lack of space. In such a case the total length is even smaller than (2). The reason is that in the calculation we add here up to q − 1 segments of length q^{−j} and that we subtract one segment of length q^{−j+1}. By (1) and (2) we conclude that Δl < q^{−t} + (λ_{0} + 1)q^{−w} + ∑_{j=w+k}^{w+m} λ_{j−w}q^{−j}.

If λ_{0} < 2q − 1, then t ≥ w + 1. Thus Δl < (λ_{0} + 1 + \frac{1}{q})q^{−w} + ∑_{j=w+k}^{w+m} λ_{j−w}q^{−j}. This and q ≤ λ_{0} imply that Δl < (1 + \frac{1}{q} + \frac{1}{q^{2}} )Δb.

If λ_{0} = 2q − 1, then Δl < (2q + 1)q^{−w} + ∑_{j=w+k}^{w+m} λ_{j−w}q^{−j} < (1 + \frac{1}{q} + \frac{1}{q^{2}} )Δb. Subcase 2.2, when at least one of the numbers μ_{1}, …, μ_{k−1} is smaller than q − 1. Let y denote the smallest number from {1, …, k − 1} such that μ_{y} < q − 1. The evaluation differs from that in Subcase 2.1 only by a different proof of (1). Now, the total length of segments of lengths between q^{−w−k+1} and q^{−w} used for the covering of (b_{i}, b_{i+1}) is at most λ_{0}q^{−w} + (q − 1) ∑_{j=w+1}^{w+y−1} q^{−j} + (q − 2)q^{−w−y} + (2q − 2) ∑_{j=w+y+1}^{w+z−1} q^{−j} + (2q − 1)q^{−w−z} + (q − 1) ∑_{j=w+z+1}^{w+k−1} q^{−j}, where z is defined at the beginning of Case 2.1 (in Fig. 6 we take y = 1 and z = 2). Instead of the last three components we may also have (2q − 2) ∑_{j=w+y+1}^{w+k−2} q^{−j} + (2q − 1)q^{−w−k+1}. The components λ_{0}q^{−w} + (q − 1) ∑_{j=w+1}^{w+y−1} q^{−j} stand for the worst possible case and in other cases we take an expression of the form (λ_{0} − 1)q^{−w} + (2q − 2) ∑_{j=w+1}^{w+v−1} q^{−j} + (2q − 1)q^{−w−v} + (q − 1) ∑_{j=w+v+1}^{w+y−1} q^{−j}. In all the variants, the total length of segments is at most (λ_{0} + 1)q^{−w} − q^{−w−k+1}.

Fig. 6. A sequence of maximum total length in Subcase 2.2

Case 3, when q^{−w} < Δb < q · q^{−w} and when Δb is not a multiple of q^{−w}. As in Subcase 1.3, the situation is the result of placing a number of segments of length q^{−w} with later growing of the current bottom close to those earlier placed segments of length q^{−w}. Of course, λ_{0} ≤ q − 1. By the description of our method we see that the last segment cannot be of length q^{−w}, this is t ≥ w + 1. We have

(1 + \frac{1}{q} + \frac{1}{q^{2}} )Δb ≥ λ_{0}q^{−w} + λ_{0}q^{−w−1} + λ_{0}q^{−w−2} + ∑_{j=w+k}^{w+m} λ_{j−w}q^{−j}.  (3)

Subcase 3.1, when the interval [p, p+q^{−w}] is not covered by a segment of length q^{−w}. Since at least one segment of length q^{−w} is put on [b_{1}, b_{i+1}], we have λ_{0} ≥ 2.

We evaluate the sum of lengths of the segments put on (b_{i}, b_{i+1}) whose lengths are between q^{−w−k+1} and q^{−w} as in Case 2, but now one less segment of length q^{−w} and one more segment of length q^{−w−1} should be taken into account (of course, λ_{0} ≥ q in Case 2 and now λ_{0} < q). Thus this sum is not greater than

(λ_{0} + \frac{1}{q})q^{−w} − q^{−w−k+1}.  (4)

Now (4) substitutes (1) from Case 2 and the value of (2) remains unchanged. Considering the sum of (4), (2) and of the length q^{−t} of the last segment we obtain

Δl < q^{−t} + λ_{0}q^{−w} + ∑_{j=w+k}^{w+m} λ_{j−w}q^{−j} + q^{−w−1}.  (5)

Since the last segment is of length at most q^{−w−1}, by (3), (5) and by λ_{0} ≥ 2 we get Δl < (1 + \frac{1}{q} + \frac{1}{q^{2}} )Δb.

Fig. 7. A sequence of maximum total length in Subcase 3.1

Subcase 3.2, when [p, p + q^{−w}] is covered by a segment of length q^{−w}. We show that

Δl < q^{−t} + λ_{0}q^{−w} + ∑_{j=w+k}^{w+m} λ_{j−w}q^{−j} + q^{−w−k}.  (6)

If b_{i+1} = p + λ_{0}q^{−w}, we show (6) in a way similar to that of showing (5). Remember that (5) is the sum of (2), (4) and of q^{−t}. The difference is that now we can place at most λ_{k} segments of length q^{−w−k}. This lowers (2) by (q − 1)q^{−w−k} = q^{−w−k+1} − q^{−w−k} and thus leads to (6).

If b_{i+1} ≠ p + λ_{0}q^{−w}, we have λ_{0} = 1 and λ_{1} ∈ {1, …, q − 1}. Moreover, b_{i+1} = p + q^{−w} + uq^{−w−1}, where u ∈ {1, …, λ_{1}}. Hence the only difference is that u segments of length q^{−w−1} are placed to the right of p + q^{−w−1} instead of to the left of p. Consequently,

(6) holds in this special situation also.

By (3) and (6) we see that if λ_{0} ≥ 2 or if k ≥ 2, then Δl < (1 + \frac{1}{q} + \frac{1}{q^{2}} )Δb.

It remains to consider the case of λ_{0} = 1 and k = 1. Observe that t ≥ w + 2. Thus Δl ≤ q^{−w−2} + q^{−w} + ∑_{j=w+k}^{w+m} λ_{j−w}q^{−j} + q^{−w−1}. Thanks to (3) we obtain Δl < (1 + \frac{1}{q} + \frac{1}{q^{2}} )Δb. □

Lemma 3. While using the (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm, assume that Δb = b_{i+1} − b_{i}, where b_{i+1} = 1, and let w be the integer for which q^{−w} < Δb ≤ q^{−w+1}. Then the total length Δl of those among the first i − 1 segments that intersect (b_{i}, 1) is less than Δb + q^{−w}.

Proof. We consider two cases. Case 1, when Δb = s · q^{−w} for s ∈ {2, …, q}. We obtain Δl < (s − 1)q^{−w} + (2q − 2) ∑_{j=w+1}^{∞} q^{−j} ≤ (s − 1)q^{−w} + (2q − 2)\frac{q}{q−1}q^{−w−1} = (s + 1)q^{−w} ≤ Δb + q^{−w}. We take into account a remark about the coefficients 2q − 2 as in Case 1 of the proof of Lemma 2. Case 2, when Δb is not a multiple of q^{−w}. We have Δb = λ_{0}q^{−w} + λ_{k}q^{−w−k} + … + λ_{m}q^{−w−m}, where λ_{0} ∈ {1, …, q − 1}, λ_{k} > 0 and λ_{m} > 0. We provide a consideration similar to the one given at the beginning of Case 3 in the proof of Lemma 2. The difference is that this time we can put a segment of length q^{−w} on the interval [p, p + q^{−w}] provided one less segment of length q^{−w−1} has been placed there. Also we do not count the last segment whose length is denoted by q^{−t} in (5). In analogy to (5), we obtain Δl < (λ_{0} + 1)q^{−w} + ∑_{j=w+k}^{w+m} λ_{j−w}q^{−j}. Thus Δl < Δb + q^{−w}. □

Theorem 1. Let q ≥ 2 be an integer. Every sequence of segments whose lengths are from the set {q^{−1}, q^{−2}, …} and whose total length is at least

1 + \frac{2}{q} − \frac{1}{q^{3}}

permits on-line covering of the interval [0, 1] by the (q +1, …, 2, q +2, …, 2q, 1)-algorithm.

Proof. It is sufficient to show that if a sequence of segments of lengths from the set {q^{−1}, q^{−2}, …} does not cover the interval [0, 1] by the algorithm, then the total length of the segments in the sequence is less than 1 + \frac{2}{q} − \frac{1}{q^{3}} . Observe that all segments from such a sequence are used during the covering process. Case 1, when b_{i} = 0 during the whole covering process. We apply Lemma 3 with Δb = 1 and w = 1. We conclude that the total length of segments placed during the covering process is less than 1 + \frac{1}{q}. This is less than 1 + \frac{2}{q} − \frac{1}{q^{3}} for every q ≥ 2. Case 2, when lim_{i→∞} b_{i} = 1. By Lemma 2 we see that the total length of segments used for the covering that have non-empty intersection with [0, b_{i}] is less than (1 + \frac{1}{q} + \frac{1}{q^{2}} )b_{i}. Thus the total length of segments used is less than 1 + \frac{1}{q} + \frac{1}{q^{2}} < 1 + \frac{2}{q} − \frac{1}{q^{3}} .

Case 3, when 0 < b′ < 1, where b′ is either lim_{i→∞} b_{i}, or b′ = b_{i} and b_{i+1} = 1. Consider the smallest integer w for which q^{−w} < 1 − b′. By Lemmas 2 and 3 we see that the total length of segments used is less than (1 + \frac{1}{q} + \frac{1}{q^{2}} )b′ + (1 − b′) + q^{−w} = 1 + (\frac{1}{q} + \frac{1}{q^{2}} )b′ + q^{−w} ≤ 1 + (\frac{1}{q} + \frac{1}{q^{2}} )(1 − q^{−w}) + q^{−w} = 1 + \frac{1}{q} + \frac{1}{q^{2}} + (1 − \frac{1}{q} − \frac{1}{q^{2}} )q^{−w}. Thus it less than 1 + \frac{1}{q} + \frac{1}{q^{2}} + (1 − \frac{1}{q} − \frac{1}{q^{2}} )q^{−1} = 1 + \frac{2}{q} − \frac{1}{q^{3}} . □

Proposition. Let q ≥ 2 be an integer. Assume that an on-line q-adic covering of the interval [0, 1] is provided by the (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm up to the total covering of this interval. Then the total length of the segments used is less than

1 + \frac{3}{q} − \frac{1}{q^{3}} .

Proof. Assume that b_{i} < 1 and b_{i+1} = 1. Let w be smallest integer w such that q^{−w} < 1−b_{i}. Of course, the segment that completes the covering of the interval [0, 1] is of length at most q^{−1}. This observation and Lemmas 2 and 3 imply that the total length of used segments is less than (1 + \frac{1}{q} + \frac{1}{q^{2}} )b′ + (1 − b′) + q^{−w} + q^{−1}. This number is smaller than 1 + \frac{3}{q} − \frac{1}{q^{3}} (see the calculation in Case 3 of the proof of Theorem 1). □

If no segment is put yet on a q-adic interval A up to a moment of a covering process, we call A vacant at this moment. If all points of A are covered, we call A totally covered at this moment. If A is not vacant and not totally covered, we call it partially covered at this moment.

Lemma 4. Assume that a process of the covering of the interval [0, 1] by segments according to the (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm is not finished yet and that the current bottom has arrived at least to a point (h − 1)q^{−1}, where h ∈ {2, …, q − 1}. Then during the covering process there is a moment at which

(i) exactly h − 1 or h among the q-adic intervals of length q^{−1} are totally covered by segments of length at most q^{−2} and no q-adic interval of length q^{−1} is partially covered, or there is a moment at which

(ii) exactly h − 1 from the q-adic intervals of length q^{−1} are totally covered by segments of length at most q^{−2} and one or two q-adic intervals of length q^{−1} are partially covered (if two, then the second one is covered by segments of length q^{−2} only).

Proof. We look at the first moment (if any) before the end of the covering process, when the current bottom attains a value b ≥ (h − 1)q^{−1}.

In order to focus our attention, we begin with taking into consideration a covering process during which only segments of length at most q^{−2} are given to us.

Assume first that (h − 1)q^{−1} ≤ b ≤ hq^{−1}. Of course, the interval [(h − 1)q^{−1}, hq^{−1}] is not totally covered before the current bottom attains b. Thus by the description of the (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm we conclude that no segment of length at most q^{−2} is placed to the right of hq^{−1} (if the current bottom is below (h − 1)q^{−1}, then a segment can be placed to the right of hq^{−1} only if the interval [(h − 1)q^{−1}, hq^{−1}] is totally covered). We see that if b < hq^{−1}, then the first h − 1 among the q-adic intervals of length q^{−1} are totally covered, the interval [(h − 1)q^{−1}, hq^{−1}] is vacant or partially covered, and the remaining q-adic intervals of length q^{−1} are vacant. We have (i), or we have (ii) with one partially covered interval of length q^{−w}. Of course, if b = hq^{−1}, then (i) holds true.

Assume now that b > hq^{−1}. As a result of placing one segment, the current bottom changes from a value b^{∗} < (h − 1)q^{−1} to b > hq^{−1}. According to our algorithm, this is possible only if the interval [(h − 1)q^{−1}, hq^{−1}] is totally covered. Thus, at the moment when the current bottom is at b^{∗}, we have exactly h − 1 intervals of length q^{−1} totally covered (by segments of length at most q^{−2}) and two such intervals partially covered. The second interval is covered by segments of length q^{−2} only. Hence (ii) is fulfilled.

If segments of length q^{−1} are given to us also, they are placed successively from the right to the left on the interval [0, 1]. It is clear that if they are put to the right of (h+1)q^{−1}, they do not affect the placement of segments of lengths at most q^{−2} considered earlier. Observe that if a segment of length q^{−1} is put on the interval [hq^{−1}, (h + 1)q^{−1}] before the current bottom arrives to b, then the current bottom is unable to attain (h − 1)q^{−1} before the end of the covering process and thus this situation cannot happen in our lemma. □

Here is the two-stage (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm. Let h ∈ {2, …, q − 1}. In the first stage of the covering process we apply the (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm. If we reach the first moment described in Lemma 4, we pass immediately to the second stage. At the beginning of the second stage, applying the (q + 1, …, 2, q + 2, …, 2q, 1)- algorithm, we place all segments of length at most q^{−2} only on the first not totally covered q-adic interval of length q^{−1} considered now as the only interval for covering by segments of length at most q^{−2}. When this interval becomes totally covered, by the (q +1, …, 2, q + 2, …, 2q, 1)-algorithm we place all segments of length at most q^{−2} on the next not totally covered q-adic interval of length q^{−1} considered now as the only interval for our covering process. We proceed similarly taking succeeding intervals of length q^{−1}. If in meantime we receive segments of length q^{−1}, we put them on q-adic intervals of length q^{−1} starting from [(q − 1)q^{−1}, 1] and then proceeding one by one to the left.

Observe that the idea of the improvement in this algorithm is in avoiding the situation that may happen if the original (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm is applied, when a segment of length q^{−1} is put on an “almost totally covered” q-adic interval of length q^{−1} and when simultaneously not many vacant q-adic intervals of length q^{−1} are covered by segments of length q^{−1} during the covering process. The price paid for the introduced improvement is a loss of efficiency in the second stage of our algorithm (just Proposition is applied instead of Lemma 2). A calculation shows that h = ⌈\frac{2}{3}q⌉ optimizes the choice of the moment at which we decide to pass to the second stage.

Theorem 2. Let q ≥ 3 be an integer. Every sequence of segments whose lengths are in the set {q^{−1}, q^{−2}, …} and whose total length is at least

1 + \frac{5}{3} · \frac{1}{q} + \frac{5}{3} · \frac{1}{q^{2}}

permits an on-line covering of the interval [0, 1]by the two-stage(q+1, …, 2, q+2, …, 2q, 1)- algorithm with h = ⌈\frac{2}{3}q⌉.

Proof. Since q ≥ 3, the requirement 2 ≤ h ≤ q − 1 of Lemma 4 and of the description of our algorithm is fulfilled. We present h = ⌈\frac{2}{3}q⌉ as \frac{2}{3}q provided q = 3c, where c is a positive integer, as h = \frac{2}{3}q + \frac{1}{3} for q = 3c + 1, and in the form \frac{2}{3}q + \frac{2}{3} for q = 3c + 2. Case 1, when the current bottom is below (h − 1)q^{−1} always before the end of the covering process. We will show that each sequence of segments of total length at least

1 + (1 + \frac{h}{q})\frac{1}{q} + \frac{h}{q} · \frac{1}{q^{2}}  (7)

permits the covering of the interval [0, 1]. Assume the opposite. Then there is a sequence of segments of total length at least (7) which does not cover [0, 1] by our algorithm. Let b′ denote the supremum of the values distinct from 1 attained by the current bottom during the covering process. By Lemma 2 we conclude that the total length of segments that have non-empty intersection with the interval (0, b′) is less than (1 + \frac{1}{q} + \frac{1}{q^{2}} )b′. By Lemma 3 we see that the total length of segments (distinct from the segment finishing the process) that have non-empty intersection with the interval (b′, 1) is less than 1 − b′ + q^{−1}. Providing an evaluation as in Case 3 of the proof of Theorem 1 and taking into account the inequality b′ < \frac{h}{q} we see that the total length of segments in our sequence is smaller than (7). This contradiction confirms that every sequence of segments of total length at least (7) permits the covering of the interval [0, 1] in Case 1. Substituting h = \frac{2}{3}q in (7), we obtain the estimate 1 + \frac{5}{3} · \frac{1}{q} + \frac{2}{3} · \frac{1}{q^{2}} . Similarly, for h = \frac{2}{3}q + \frac{1}{3} we get 1 + \frac{5}{3} · \frac{1}{q} + \frac{1}{q^{2}} + \frac{1}{3} · \frac{1}{q^{3}} , and for h = \frac{2}{3}q + \frac{2}{3} we get 1 + \frac{5}{3} · \frac{1}{q} + \frac{4}{3} · \frac{1}{q^{2}} + \frac{2}{3} · \frac{1}{q^{3}} .

Case 2, when the current bottom attains at least (h − 1)q^{−1} before the end of the covering process. According to Lemma 4 and to the description of the algorithm, when we pass to the second stage, (i) or (ii) holds true. We will assume (ii) with the exception of one sentence at the end of Subcase 2.1 where we take care about the possibility (i).

Assume that we have two partially covered intervals (if we have one only, then we can take the first vacant q-adic interval of length q^{−1} in the part of the second partially covered interval). Denote by T the rightmost one of our two partially covered intervals. Subcase 2.1, when T is not covered by a segment of length q^{−1} during the covering process. We apply Lemma 2. We also apply Proposition and Theorem 1 but for the scaled down by a factor of q image of the original situation. They are just applied for the process of the covering of separate q-adic intervals of length q^{−1} by q-adic segments of length at most q^{−2}. This explains the factors \frac{1}{q} in the following estimate: (1 + \frac{1}{q} + \frac{1}{q^{2}} )\frac{h−1}{q} + (q − h)(1 + \frac{3}{q} − \frac{1}{q^{3}} )\frac{1}{q} +(1+ \frac{2}{q} − \frac{1}{q^{3}} )\frac{1}{q}. Consequently, the interval [0, 1] can be covered if the total length of segments in a sequence is at least

1 + (3 − 2 · \frac{h}{q}) · \frac{1}{q} + (1 + \frac{h}{q}) · \frac{1}{q^{2}} + ( − 2 + \frac{h}{q}) · \frac{1}{q^{3}} − \frac{1}{q^{4}} .  (8)

Substituting h = \frac{2}{3}q in (8), we obtain the estimate 1 + \frac{5}{3} · \frac{1}{q} + \frac{5}{3} · \frac{1}{q^{2}} − \frac{4}{3} · \frac{1}{q^{3}} − \frac{1}{q^{4}} . Similarly, for h = \frac{2}{3}q + \frac{1}{3}, we get the estimate 1 + \frac{5}{3} · \frac{1}{q} + \frac{1}{q^{2}} − \frac{1}{q^{3}} − \frac{2}{3} · \frac{1}{q^{4}} , and for h = \frac{2}{3}q + \frac{2}{3} we obtain 1 + \frac{5}{3} · \frac{1}{q} + \frac{1}{3} · \frac{1}{q^{2}} − \frac{2}{3} · \frac{1}{q^{3}} − \frac{1}{3} · \frac{1}{q^{4}} .

If (i) holds true with h totally covered intervals, then in place of (8) we have (1 + \frac{1}{q} + \frac{1}{q^{2}} )\frac{h}{q} + (q − h − 1)(1 + \frac{3}{q} − \frac{1}{q^{3}} )\frac{1}{q} + (1 + \frac{2}{q} − \frac{1}{q^{3}} )\frac{1}{q} which is smaller by 2 · \frac{1}{q^{2}} − \frac{1}{q^{3}} − \frac{1}{q^{4}} than (8), and in the case of h − 1 totally covered intervals in (i) we get even a smaller value. Subcase 2.2, when T is covered by a segment of length q^{−1} during the covering process. By Lemma 4, by the description of the two-stage algorithm and by the assumption of our subcase we see that before a segment of length q^{−1} covers T, segments of length q^{−2} only are put on T. Of course, the number of them is at most q − 1. We take this into account when we provide a calculation similar to that from Subcase 1.1. We see that the interval [0, 1] can be covered if the total length of segments in a sequence is at least (1 + \frac{1}{q} + \frac{1}{q^{2}} )\frac{h−1}{q} + (q − 1)\frac{1}{q^{2}} + (q − h)\frac{1}{q} + (1 + \frac{2}{q} − \frac{1}{q^{3}} )\frac{1}{q} = 1 + (1 + \frac{h}{q}) · \frac{1}{q} + \frac{h}{q} · \frac{1}{q^{2}} − \frac{1}{q^{3}} − \frac{1}{q^{4}} . Since this is smaller than (7), we can disregard Subcase 2.2 in further calculations. Comparing (7) and (8) (or rather the three pairs of corresponding particular estimates resulting by (7) and (8)) we see that if q has the form 3c, we get the estimate

1 + \frac{5}{3} · \frac{1}{q} + \frac{5}{3} · \frac{1}{q^{2}} − \frac{4}{3} · \frac{1}{q^{3}} − \frac{1}{q^{4}} .  (9)

Similarly, if q has the form 3c + 1, we obtain the estimate

1 + \frac{5}{3} · \frac{1}{q} + \frac{1}{q^{2}} + \frac{1}{q^{3}}  (10)

and if q has the form 3c + 2, we obtain

1 + \frac{5}{3} · \frac{1}{q} + \frac{4}{3} · \frac{1}{q^{2}} + \frac{2}{3} · \frac{1}{q^{3}} .  (11)

Of course, (9)–(11) are smaller than 1 + \frac{5}{3} · \frac{1}{q} + \frac{5}{3} · \frac{1}{q^{2}} for every q ≥ 3. □

The formulas (9)–(11) are more precise than the simple formula in Theorem 2. They give a better estimate than Theorem 1 for q ≥ 6.

We can improve the two-stage (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm by applying the two-stage approach additionally for the covering of some q-adic intervals of length q^{−2}. We apply our two-stage algorithm with an h = h_{1} ∈ {2, …, q−1}. The difference is that in the second stage, for the covering of the q-adic intervals of length q^{−2} we apply the reduced in size by a factor of q variant of the two-stage (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm (with h_{2} = ⌈\frac{2}{3}q⌉) instead of the (q + 1, …, 2, q + 2, …, 2q, 1)-algorithm. An interval of length q^{−2} is q times shorter than the interval of length q^{−1}, and we are putting q times shorter segments (now they are of lengths q^{−2}, q^{−3}, … instead of lengths q^{−1}, q^{−2}, …).

Let us estimate the efficiency of the above algorithm in analogous way as in the proof of Theorem 2. Again we have two cases.

The first case is when the current bottom is below (h − 1)q^{−1} always before the end of the covering process. We repeat the considerations of Case 1 of Theorem 2. We conclude that every sequence of segments of total length at least (7) permits the covering.

The second case is when the current bottom attains at least (h − 1)q^{−1} before the end of the covering process. Again we apply Lemma 4 and we consider two subcases analogous to Subcases 2.1 and 2.2 of the proof of Theorem 2. In the first subcase we apply Lemma 2, Theorem 2 and a modification of Proposition related to Theorem 2 (instead to Theorem 1). We provide an analogous calculation like in Subcase 2.1 of the proof of Theorem 2: (1 + \frac{1}{q} + \frac{1}{q^{2}} )\frac{h−1}{q} + (q − h)(1 + \frac{8}{3} · \frac{1}{q} + \frac{5}{3} · \frac{1}{q^{2}} )\frac{1}{q} + (1 + \frac{5}{3} · \frac{1}{q} + \frac{5}{3} · \frac{1}{q^{2}} )\frac{1}{q}. We see that the interval [0, 1] can be covered if the total length of segments in a sequence is at least

1 + (\frac{8}{3} − \frac{5}{3} · \frac{h}{q}) · \frac{1}{q} + (\frac{7}{3} − \frac{2}{3} · \frac{h}{q}) · \frac{1}{q^{2}} + \frac{2}{3} · \frac{1}{q^{3}} .  (12)

In the second subcase we again obtain an estimate slightly better than in the first case.

For every specific q ≥ 3 we are looking for the best choice of h_{1} in the part of h, so that the greater of the values (7) and (12) is minimized. When we substitute h_{1} = ⌈\frac{5}{8}q⌉ for h in (7) and in (12), then they both become at most 1 + \frac{13}{8} · \frac{1}{q} plus a constant times \frac{1}{q^{2}} . We see that the component \frac{5}{3} · \frac{1}{q} from Theorem 2 is lowered to \frac{13}{8} · \frac{1}{q}. We can still improve the algorithm by applying the two-stage approach to shorter q-adic intervals. We omit here the calculation that shows that a proper application of this method lowers the crucial component to \frac{34}{21} · \frac{1}{q} when also q-adic intervals of length q^{−3} are covered in two stages, and to \frac{89}{55} · \frac{1}{q} when additionally the q-adic intervals of length q^{−4} are covered in two stages. An evaluation shows that the sequence 2, \frac{5}{3}, \frac{13}{8}, \frac{34}{21}, \frac{89}{55}, … of our factors tends to \frac{1}{2}(1 + \sqrt{5}) = 1.61803 . . ..

Each on-line 2^{d}-adic algorithm which permits a covering of the unit interval by sequences of segments of total length l induces an on-line algorithm which permits a covering of the unit cube of E^{d} by every sequence of cubes of total volume 2^{d}l. This construction invented in [5] is described in Part 3 of [3] and in Part 6.2 of [7]. Thus Theorem 2 implies the following result.

Theorem 3. Every sequence of cubes of sides at most 1 in E^{d} whose total volume is at least

2^{d} + \frac{5}{3} + \frac{5}{3} · 2^{−d}

permits an on-line covering of the unit cube of E^{d}.

We see that the assumption about the total volume of a sequence of cubes is improved from almost 2^{d} + 3 in [3] to slightly over 2^{d} + \frac{5}{3}. Despite of the on-line restriction, this value is very close to the best possible off-line estimate 2^{d} − 1 (see [2]). In particular, the estimate for the three dimensional case is lowered from 10.657 … to 9.875 . . .. But if we apply (11), which is more precise for q = 8 than the estimate in the formulation of Theorem 2, we get a further improvement down to 9.843 . . ..

References

[1] Csirik, J.; Woeginger, G. J.: On-line packing and covering problems. Lect. Notes Comput. Sc. 1442 (1998), 147–177.

[2] Groemer, H.: Covering and packing by sequences of convex sets. Discrete Geometry and Convexity, Annals of the New York Academy of Sciences, Vol. 440 (1985), 262– 278.

[3] 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. Algebra Geom. 37 (1996), 51–65. Zbl 0863.52010

[4] Januszewski, J.; Lassak, M.; Rote, G.; Woeginger, G.: Solution of Problem 74. Math. Semesterber. 43 (1996), 94–100.

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

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

[7] Lassak, M.: A survey of algorithms for on-line packing and covering by sequences of

convex bodies. Bolyai Society Mathematical Studies 6 (1997), 129–157.

Zbl 0883.52014

Received March 1, 2001; revised version June 20, 2001