On-Line q-adic Covering by the Method of the n-th Segment and its Application to On-Line Covering by Cubes

Janusz Januszewski^{1}, Marek Lassak^{1}, Günter Rote^{2}, and Gerhard Woeginger^{2}

1 Instytut Matematyki i Fizyki ATR Kaliskiego 7, 85-796 Bydgoszcz, Poland 2 Institut für Mathematik, Technische Universität Graz Steyergasse 30, A-8010 Graz, Austria

Abstract. We prove that in Euclidean d-space, every sequence of cubes with total volume 2^{d} + 3 is able to cover on-line the unit cube. The proof is based on an on-line q-adic method of covering the unit segment by segments of lengths of the form q^{−r}, where q ≥ 2 and r ≥ 1 are integers. The fact that this method is q-adic means that every segment has to be placed in such a way that both end-points are at points that are multiples of the length of the segment.

We say that a sequence Q_{1}, Q_{2}, … of subsets of Euclidean space E^{d} permits a covering of the 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}, . . .. A survey of results about covering of convex bodies by sequences of convex bodies is provided by Groemer [2].

An on-line covering problem consists in finding the motions τ_{1}, τ_{2}, …, under the condition that we are given every set Q_{i}, with i > 1, only after the motion τ_{i−1} has been provided. We learn the set Q_{1} at the beginning. On-line covering problems by convex bodies are considered in a number of papers. The first result about on-line covering the unit cube by cubes was obtained by Kuperberg [5]. This result was improved in [3,4] and the present paper provides a further improvement. The reader may compare the above on-line assumption with that in the area of bin-packing problems (see the survey paper [1]).

In this paper we first deal with a specially restricted one-dimensional covering problem and then apply it to higher-dimensional problems.

By [x, y] we denote the closed segment with end-points x and y, where x < y. The symbol (x, y) denotes the corresponding open segment.

Let q be an integer greater or equal to 2. By the on-line q-adic covering problem of the unit segment [0, 1] we mean the problem of on-line covering the segment [0, 1] by a sequence of closed segments S_{i} of lengths δ_{i}, where δ_{i} ∈ {q^{−1}, q^{−2}, …}, and where the motions τ_{i} are restricted such that 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, . . ..

1 Supported in part by Komitet Badan Naukowych (Committee of Scientific Research), Grant Number 2 2005 92 03.

1. The method of the n-th segment Let n ≥ 2 be an integer. At every moment of the covering process we determine the greatest number b ∈ [0, 1] such that the whole segment [0, b] is covered. Assume that we are given a segment S from our sequence and let q^{−r} be the length of this segment. Denote by a the greatest number from amongst 0, …, q^{r} − 1 such that aq^{−r} ≤ b. If the interval [(a + k − 1)q^{−r}, (a + k)q^{−r}], where k ∈ {1, 2, …}, is a subset of [0, 1], then we call it the k-th interval . Let c be the greatest number from amongst a, …, a + n − 1 such that the segment T = [cq^{−r}, (c + 1)q^{−r}] is contained in [0, 1] and such that T is not yet totally covered. The segment S is put on T, i. e., we provide a motion τ such that τS = T. (In other words, we successively try the n-th segment, the (n − 1)-st segment, and so on, until we find an interval not totally covered.) We finish the process when the whole segment [0, 1] is covered. The above described method is called the n-th segment method. It is an on-line algorithm for q-adic covering.

We will mainly be interested in the cases n = q + 1, n = q + 2, and n = q + 3, because these three values give the best performance ratio for all values of q.

Let us first introduce some notation that will be used in the sequel. We imagine the segment [0, 1] laid out horizontally with 0 on the left end and 1 on the right end. For every integer i > 1 we denote by b_{i} the greatest number in the segment [0, 1] such that the segment [0, b_{i}] is covered by the union of segments τ_{h}S_{h} for h < i. Moreover, let b_{1} = 0. We call b_{i} the current bottom; we choose this name because our notion takes similar tasks in the considerations as the notion of the current bottom in some other papers where a cube or a box is filled from bottom to top.

We start with a somewhat technical lemma.

LEMMA 1. Consider the n-th segment method for some n > q. Let p be a multiple of q^{−w} for some w such that 0 < p < 1. Assume that at some point of the algorithm, the interval [0, p] has not been completely covered yet. For j ≥ 0 let ν_{j} be the number of segments of length q^{−w−j} which the algorithm has placed to the right of p. If ν_{0}, …, ν_{ℓ} ≥ n − 2 for some ℓ ≥ 0, then at most one of these ℓ + 1 numbers is equal to n − 1. If, in addition, one of the numbers ν_{0}, …, ν_{ℓ} equals n − 1, then the interval [p, p + q^{−w+1}] is completely covered.

Proof. Assume that ν_{j} = n−1 for some j and ν_{0}, …, ν_{j−1} ≥ n−2. We want to show that ν_{0} = ⋯ = ν_{j−1} = n − 2 and that the whole interval [p, p + q^{−w+1}] is covered. Since p is a multiple of q^{−w−j}, the equation ν_{j} = n − 1 can only hold if the n − 1 segments of length q^{−w−j} to the right of p are the adjacent intervals [p, p + q^{−w−j}], …, [p + (n − 2)q^{−w−j}, p + (n − 1)q^{−w−j}]. Since n − 1 ≥ q, this means that the interval [p, p + q^{−w−j+1}] is completely covered. If we now look at ν_{j−1}, we see that the possible positions for the segments of length q^{−w−j+1} are the n−1 intervals [p, p+q^{−w−j+1}], …, [p+(n−2)q^{−w−j+1}, p+(n−1)q^{−w−j+1}]. Among them, the first interval is not possible because it has been covered completely by smaller segments. Thus we conclude that ν_{j−1} = n − 2, and we know that [p, p + q^{−w−j+2}] is completely covered. In this way we proceed inductively to ν_{j−2}, …, ν_{0}, and the lemma is proved.

During the course of the algorithm, the algorithm makes progress by gradually advancing the current bottom b_{i}. The following lemma relates this progress to the sum of the lengths of segments which are used to cover the area to the left of b_{i}.

LEMMA 2. Consider the n-th segment method for some n with q < n ≤ 2q. Assume that i ≥ 1 and b_{i} < b_{i+1} < 1 and put Δb = b_{i+1} − b_{i}. Denote by Δl the total length of those from the segments τ_{1}S_{1}, …, τ_{i}S_{i} which have non-empty intersection with (b_{i}, b_{i+1}). We have

Δl < (1 + \frac{1}{q − 1} + \frac{1}{n − 1} − \frac{1}{(q − 1)(n − 1)})Δb.  (1)

Proof. Denote by w the smallest positive integer such that a segment of length q^{−w} has been used for the covering of the segment (b_{i}, b_{i+1}). From the description of the method we see that

q^{−w} < Δb ≤ nq^{−w}.

Thus we can represent Δb in the form

Δb = ∑_{j=0}^{m} λ_{j}q^{−w−j},

where λ_{0} ∈ {1, …, n}. Moreover, if m ≥ 1, then λ_{1}, …, λ_{m} ∈ {0, …, q − 1}, and λ_{m} ≥ 1.

For j = 0, 1, 2, …, denote by μ_{j} the number of segments of length q^{−w−j} from amongst τ_{1}S_{1}, …, τ_{i−1}S_{i−1} which are used for covering (b_{i}, b_{i+1}). Let the length of the last segment S_{i} be q^{−r} = δ_{i}. Of course, 0 ≤ μ_{j} ≤ n − 1 for j = 0, 1, 2, …, and μ_{0} > 0 unless r = w. We can write Δl as follows:

Δl = q^{−r} + ∑_{j=0}^{∞} μ_{j}q^{−w−j}

The interval (b_{i}, b_{i+1}) can be covered in different ways depending on the size of Δb. We distinguish four cases.

Case 1, when Δb = nq^{−w}. We have μ_{j} ≤ n − 1 for j = 0, 1, 2, . . .. Thus

Δl < q^{−r} + (n − 1) ∑_{j=w}^{∞} q^{−j} ≤ q^{−w} + (n − 1) ∑_{j=w}^{∞} q^{−j} = \frac{nq − 1}{q − 1}q^{−w}

which together with (2) implies (1).

Case 2, when (n−1)q^{−w} ≤ Δb < nq^{−w}. We have λ_{0} = n−1. It follows that b_{i+1} must be a multiple of q^{−w}: The region immediately left of b_{i+1} must be covered by a segment of length q^{−w} because shorter segments cannot “reach” far enough to the right from b_{i} or from the left of b_{i}, since n ≤ 2q. Let us first assume Δb > (n − 1)q^{−w}. In this case, let k denote the smallest number from amongst 1, …, m such that λ_{k} > 0. Then we have

Δb ≥ (n − 1)q^{−w} + λ_{k}q^{−w−k} ≥ (n − 1)q^{−w} + q^{−w−k}.  (2)

Since b_{i+1} is a multiple of q^{−w} and b_{i} = b_{i+1} − Δb, the point b_{i} is close to a multiple p of q^{−w}. More precisely,

p − q^{−w−k+1} < b_{i} ≤ p − q^{−w−k}.

It follows that all segments of length between q^{−w−k+1} and q^{−w} among τ_{1}S_{1}, …, τ_{i−1}S_{i−1} which have been used to cover (b_{i}, b_{i+1}) must lie to the right of p. Since none of the segments of these lengths to the right of p can lie to the right of b_{i+1}, Lemma 1 can be applied, with ν_{i} = μ_{i} for i = 0, …, k − 1. We distinguish two subcases: either all numbers μ_{0}, …, μ_{k−1} are at least n−2, or there is some first element μ_{z} in the sequence μ_{0}, …, μ_{k−1} which is less than n − 2. In the first subcase at most one μ_{j} with 0 ≤ j < k equals n − 1, and

Δl ≤ q^{−r} + (n − 2) ∑_{j=w}^{w+k−1} q^{−j} + q^{−w} + (n − 1) ∑_{j=w+k}^{∞} q^{−j}.  (3)

The term q^{−w} accounts for the μ_{j} with 0 ≤ j < k which is possibly equal to n − 1. In the second subcase we have

Δl ≤ q^{−r} + (n − 2) ∑_{j=w}^{w+z−1} q^{−j} + q^{−w} + (n − 3)q^{−w−z} + (n − 1) ∑_{j=w+z+1}^{∞} q^{−j}.

(For z = 0, the “empty sum” ∑_{j=w}^{w+z−1} is taken as zero.) The term q^{−w} stands for the same reason as above. One checks that this last bound is weakly increasing in z, and for the maximum z = k − 1 it is smaller than the bound of (3). Hence (3) holds in both subcases, and we get from (3), using the relation q^{−r} ≤ q^{−w},

\begin{aligned}Δl & < 2q^{−w} + (n − 2) ∑_{j=w}^{∞} q^{−j} + ∑_{j=w+k}^{∞}q^{−j} = q^{−w} (2 + \frac{(n − 2)q}{q − 1} ) + q^{−w−k} · \frac{q}{q − 1} \\ & ≤ q^{−w} · \frac{nq − 2}{q − 1} + q^{−w−k} · \frac{nq − 2}{(q − 1)(n − 1)} \end{aligned}

which together with (2) shows (1).

By letting k grow one can conclude that in this case the bound is tight. In the next section we construct examples where the above bound is the true expression for the ratio between Δl and Δb, thus showing that the ratio in the lemma cannot be improved.

The above argument worked under the assumption Δb > (n − 1)q^{−w}. For the case Δb = (n − 1)q^{−w} we may modify the proof by “symbolically” setting k = ∞. Correspondingly we set q^{−w−k} = 0, etc. The reader may check, this leads to a valid proof of (1).

Case 3, when 2q^{−w} ≤ Δb < (n − 1)q^{−w}. It is easy to see that 2 ≤ λ_{0} ≤ n − 2.

In this case the μ_{0} segments of length q^{−w} in (b_{i}, b_{i+1}) must have been placed before b_{i} was reached. In fact, they must have been placed at at time t when b_{t} was less than b_{i+1} − (n − 1)q^{−w} because otherwise such a segment would have been placed to the right of b_{i+1}. By the same reason, the last segment q^{−r} cannot be q^{−w}, and thus q^{−r} ≤ q^{−w−1}. Clearly μ_{0} ≤ λ_{0}.

Subcase 3.1; μ_{0} = λ_{0} = n − 2. In this case Δb ≠ λ_{0}q^{−w} because otherwise the μ_{0} disjoint segments of length q^{−w} would cover (b_{i}, b_{i+1}) completely, and the segment of length q^{−w} which covers (b_{i}, b_{i} + q^{−w}) would be the last segment, which we have excluded. Therefore we can define the smallest number k from amongst 1, …, m such that λ_{k} > 0. Thus

Δb ≥ λ_{0}q^{−w} + λ_{k}q^{−w−k}.  (4)

Let us show the inequality

μ_{1} ≤ (n − 1 − q) + λ_{1}.  (5)

To do this, look at the possible positions for the μ_{1} segments of length q^{−w−1}. To the left of the point p := b_{i+1} − λ_{0}q^{−w} there are λ_{1} possible positions which are contained in [b_{i}, b_{i+1}]. An interval of length q^{−w−1} can be placed to the right of p only if that position has not been previously covered by an interval of length q^{−w}. As we have seen above, the μ_{0} = λ_{0} segments of length q^{−w} have been placed to fill the interval (p, b_{i+1}) completely at a time t when b_{t} was smaller than b_{i+1} − (n − 1)q^{−w} = b_{i+1} − (λ_{0} + 1)q^{−w} = p − q^{−w}. At such a time, the endpoint of rightmost possible position for a segment of length q^{−w−1} is less than b_{t} + nq^{−w−1} ≤ p − q^{−w} + nq^{−w−1} ≤ p + (n − q)q^{−w−1}. Therefore we get at most n − q − 1 possible positions to the right of p. Together with the λ_{k} positions left of p this gives the inequality (5).

By a similar argument we show that μ_{j} ≤ λ_{j} for 1 < j ≤ k. In this case the rightmost possible position for a segment of length q^{−w−j} is less than p − q^{−w} + nq^{−w−1} ≤ p, since n ≤ q^{2} and j ≥ 2. For j > k we clearly have μ_{j} ≤ n − 1.

As a consequence of these inequalities for μ_{j} we obtain

Δl < q^{−w−1} + λ_{0}q^{−w} + (n − q − 1)q^{−w−1} + λ_{k}q^{−w−k} + (n − 1) ∑_{j=w+k+1}^{∞} q^{−j}

= q^{−w} · (n − 2 + n/q − 1) + q^{−w−k} · (λ_{k} + \frac{n − 1}{q − 1})

< q^{−w} · (n − 2 + n/q − 2/q) + q^{−w−k}λ_{k} + q^{−w−1} · \frac{n − 1}{q − 1} + \frac{q(q − 2)(n − 2) − (n − 1)}{q(q − 1)(n − 1)}

= q^{−w}(n − 2) · (1 + \frac{1}{q − 1} + \frac{1}{n − 1} − \frac{1}{(q − 1)(n − 1)}) + q^{−w−k}λ_{k},

which together with (4) gives (1). The last term which has been added in the third line is positive only for q ≥ 3. For q = 2, a different calculation must be used. Starting with the second line above, we can write

Δl < 2^{−w}(n − 2) · 3/2 + 2^{−w−k} (λ_{k} + n − 1)

= 2^{−w}(n − 2) · 3/2 + +2^{−w−k} (n − 1 − λ_{k}) + 2^{−w−k} · 2λ_{k}

≤ 2^{−w}(n − 2) · 3/2 + 2^{−w−1}(n − 2) + 2^{−w−k} · 2λ_{k}

= (2^{−w}(n − 2) + 2^{−w−k}λ_{k}) · 2 ≤ Δb · 2 = Δb · (1 + \frac{1}{q − 1} + \frac{1}{n − 1} − \frac{1}{(q − 1)(n − 1)})

Subcase 3.2; 2 ≤ μ_{0} = λ_{0} < n − 2. Again we must have Δb ≠ λ_{0}q^{−w}, and we can define k as in the previous subcase. In contrast to that case, we can show the stronger relation μ_{1} ≤ λ_{1}. Arguing as in Subcase 3.1, with the same definition of p, we conclude that b_{t} < b_{i+1} − (n − 1)q^{−w} ≤ b_{i+1} − (λ_{0} + 2)q^{−w} = p − 2q^{−w}. Since n ≤ 2q, there are no possible positions to the right of p for segments of size at most q^{−k−1}. So we have μ_{j} ≤ λ_{j} for j = 1, …, k, and μ_{j} ≤ n − 1 for j > k. We obtain

Δl < q^{−w−1} + λ_{0}q^{−w} + (λ_{k})q^{−w−k} + (n − 1) ∑_{j=w+k+1}^{∞} q^{−j}

= q^{−w}(λ_{0} + 1/q) + q^{−w−k} · (λ_{k} + \frac{n − 1}{q − 1})

= q^{−w}(λ_{0} + \frac{1}{q} · (1 + \frac{n − 2}{q − 1}) + q^{−w−k} · (λ_{k} + \frac{1}{q − 1})

≤ q^{−w}(λ_{0} + \frac{λ_{0}}{t − 1} · (1 + \frac{n − 2}{q − 1}) + q^{−w−k} · (λ_{k} + \frac{λ_{k}}{q − 1})

= q^{−w}λ_{0} · (1 + \frac{1}{q − 1} + \frac{1}{n − 1} − \frac{1}{(q − 1)(n − 1)}) + q^{−w−k}λ_{k} · (1 + \frac{1}{q − 1}) ,

which together with (4) proves (1).

Subcase 3.3; 1 ≤ μ_{0} ≤ λ_{0} − 1 = n − 3. Since n ≥ 4 we must have q ≥ 3. We have μ_{j} ≤ n − 1 for j ≥ 1 and get

Δl < q^{−w−1} + (λ_{0} − 1)q^{−w} + (n − 1) ∑_{j=w+1}^{∞} q^{−j} = q^{−w} (\frac{1}{q} + n − 3 + \frac{n − 1}{q − 1})

= q^{−w} · (n − 2 + \frac{n − 2}{q − 1} + \frac{1}{q} + \frac{1}{q − 1} − 1)

< q^{−w}(n − 2) · (1 + \frac{1}{q − 1}) ≤ Δb (1 + \frac{1}{q − 1}) ,

from which (1) follows.

Subcase 3.4; 1 ≤ μ_{0} ≤ λ_{0} − 1 < n − 3. Again, λ_{0} ≥ 2. Let us denote p = b_{i+1} − λ_{0}q^{−k}. We show that in fact μ_{0} = λ_{0} − 1, the μ_{0} segments of length q^{−k} completely cover the interval [p + q^{−k}, b_{i+1}], and they lie disjoint from all other intervals. First of all, since n ≤ 2q, no segment shorter than q^{−w} reach far enough to the right from b_{i} or from the left of b_{i}, in order to cover the interval [p + q^{−w}, p + 2q^{−w}] completely. This is a fortiori true for the λ_{0} − 2 intervals which lie between p + 2q^{−w} and b_{i+1}. Since we have at most λ − 1 segments of length q^{−k} available, all of them must be used to cover these intervals, because otherwise they would remain uncovered. Secondly, we have previously seen that, before the last segment of length q^{−k} was placed inside (p, b_{i+1}), the value of b_{t} must have been less than b_{i+1} − (n − 1)q^{−w}. Therefore a segment of length q^{−w−k} for k ≥ 1 cannot cover anything to the right of b_{i+1} − (n − 1)q^{−w} + nq^{−w−k} ≤ p before all μ_{0} segments of length q^{−k} are placed. Therefore these μ_{0} segments of length q^{−k} lie disjoint from all other segments.

From this it follows that μ_{0}q^{−k} + μ_{1}q^{−k−1} ≤ λ_{0}q^{−k} + λ_{1}q^{−k−1} We have thus

Δl < q^{−w−1} + μ_{0}q^{−k} + μ_{1}q^{−k−1} + (n − 1) ∑_{j=w+2}^{∞} q^{−j}

≤ λ_{0}q^{−k} + λ_{1}q^{−k−1} + \frac{n − 1}{q} \frac{1}{(q − 1)}q^{−k} ≤ Δb + λ_{0}q^{−k} \frac{1}{(q − 1)} < Δb (1 + \frac{1}{(q − 1)}) ,

and we are done.

Case 4, when q^{−w} ≤ Δb < 2q^{−w}. In order to avoid splitting up further cases, we reduce this case to the proof of the preceding cases. As in Case 3, we conclude that the last segment was not of length q^{−w}, and therefore μ_{0} = λ_{0} = 1. Let the segment of length q^{−w} which was placed inside [b_{i}, b_{i+1}] be at position [p, p + q^{−w}]. We reduce the proof of this case to the other cases by modifying the sequence S_{1}, …, S_{i} of intervals. We replace the segment of length q^{−w} which the algorithm placed at position [p, p + q^{−w}] by some smaller segments.

We will now describe how we modify the sequence S_{1}, …, S_{i}. We start the algorithm with no segment placed and go through the given sequence of segments step by step. Before each segment (including the start of the algorithm), we try to determine the smallest index k ≥ 1 such that the n-th segment position for a segment of length q^{−w−k} would fall into an uncovered portion of the interval [p, b_{i+1}]. If we find such a k, we generate segments of length q^{−w−k} and insert them into the sequence of segments at the current point. We insert the right number of these segments such that, when the algorithm has processed them, the interval between p and the n-th position for q^{−w−k} is completely covered. Then we proceed to the next segment in the original sequence. If it is the segment of length q^{−w} which would go into the position [p, p + q^{−w}] or (in the case, when b_{i+1} > p + q^{−w}) if it is the segment of length q^{−w−1} which would go into the segment [p + q^{−w}, b_{i+1}], then we skip it.

It can be seen that we will always have k = 1 or k = 2. If some choice of k is not possible because its n-th position is already covered or lies to the left of p, then no larger choice of k is possible. The choice of k = 1 may be excluded also for the reason that the n-th segment position for q^{−w−1} may lie to the right of b_{i+1}. But since n ≤ 2q and Δb ≥ q^{−w}, the n-th segment position for q^{−w−2} lies always to the left of b_{i+1}. So, if k = 1 and k = 2 are both not possible, then no larger choice of k is possible. Moreover, once k = 2 has been chosen, k = 1 can never be chosen again. It follows that the new segments which are inserted have disjoint interiors.

When the algorithm processes the modified sequence of segments, the successive values of b_{j} are unchanged, except that the final value is some b′_{i+1} with p ≤ b′_{i+1} ≤ b_{i+1}. (We use the subscript i + 1 although i may no longer reflect the number of segments of the modified sequence which have been processed.) In particular Δb′ is b′_{i+1} −b_{i} with the same value b_{i} as before.

For the modified sequence we have

Δb′ = b′_{i+1} − b_{i} = Δb − (b_{i+1} − b′_{i+1}).

Instead of the interval [p, b_{i+1}], which was previously covered without overlap, we have now the interval [p, b′_{i+1}], which is covered without overlap. Moreover, to the right of b′_{i+1} no new segments are added. To the left of p and to the right of b_{i+1} nothing has changed. Consequently, for the modified value Δl′ of Δl we get

Δl′ = Δl − (b_{i+1} − p) + (b′_{i+1} − p) = Δl − (b_{i+1} − b′_{i+1}),

If Δb′ is greater or equal than two times the length of the longest segment used for the covering of the segment (b_{i}, b′_{i+1}), then we apply the preceding cases of our lemma to the modified sequence of segments;. from Δl′ < (1 + \frac{1}{q−1} + \frac{1}{n−1} − \frac{1}{(q−1)(n−1)})Δb′ we conclude that Δl < (1 + \frac{1}{q−1} + \frac{1}{n−1} − \frac{1}{(q−1)(n−1)})Δb. In the opposite case, a number of times we apply the procedure of modyfying the sequence of intervals. Just up to the moment when the corresponding Δb′ becomes at least two times the length of the corresponding longest segment used for the coverig of the corresponding segment (b_{i}, b′_{i+1}). The repeating of this procedure ends after a finite number of times because Δb′ ≥ p − b_{i} > 0.

The previous lemma has considered the intervals to the left of the current b_{i}; the next lemma deals with the intervals that remain to the right of b_{i}.

LEMMA 3. Consider the n-th segment method for some n with q < n ≤ 2q. Assume that for some i > 0 we have b_{i} < 1. Put Δb = 1 − b_{i}. Denote by w the integer for which q^{−w} < Δb ≤ q^{−w+1}. Then the total length Δl of the segments from amongst τ_{1}S_{1}, τ_{2}S_{2}, …, τ_{i−1}S_{i−1} having non-empty intersection with (b_{i}, 1) is less than

Δb + (\frac{n − 2}{q − 1}) q^{−w}.

Moreover, if Δb < 2q^{−w}, then we have the stronger bound

Δb + (\frac{n − 2}{q − 1} − \frac{n − q − 1}{q}) q^{−w}.

Proof. Let us represent Δb in the form ∑_{j=0}^{m} λ_{j}q^{−w−j}, where 1 ≤ λ_{0} ≤ q, 0 ≤ λ_{j} ≤ q − 1 for 0 < j < m, and 0 < λ_{m}. Denote by F the family of those among the segments τ_{1}S_{1}, …, τ_{i−1}S_{i−1} which have non-empty intersection with (b_{i}, 1]. We know that a segment from F cannot contain the point b_{i} because otherwise b_{i} would be bigger.

Denote by μ_{j} the number of segments of length q^{−w−j} in F for j = 0, 1, 2, . . .. We may assume that F does not contain segments of length over q^{−w}, that μ_{0} ≤ λ_{0}, and that μ_{j} ≤ q for j = 1, 2, . . .. If any of these assumptions is not satisfied, we immediately see that the point b_{i} is covered by segments from the family F and thus we get a contradiction.

If μ_{j} ≤ n − 2 for all j ≥ 1 then we have

Δl = ∑_{j=0}^{∞} μ_{j}q^{−w−j} ≤ μ_{0}q^{−w} + (n − 2) ∑_{j=1}^{∞} q^{−w−j} ≤ λ_{0}q^{−w} + q^{−w} · \frac{n − 2}{q − 1},

and the proof is completed. Otherwise, let z be the smallest non-negative integer such that μ_{z} = n − 1. If z = 0, then [b_{i}, 1] is covered, so assume that z ≥ 1. Using the inequalities μ_{1}, …, μ_{z−1} ≤ n − 2 and μ_{z}, μ_{z+1}, … ≤ n − 1 we obtain

\begin{aligned}Δl & = ∑_{j=0}^{∞} μ_{j}q^{−w−j} ≤ μ_{0}q^{−w} + (n − 2) ∑_{j=1}^{z−1} q^{−w−j} + (n − 1) ∑_{j=z}^{∞} q^{−w−j} \\ & = μ_{0}q^{−w} + \frac{n − 2}{q − 1} · q^{−w} + (1 + \frac{1}{q − 1}) q^{−w−z} \end{aligned}

Similarly, using the inequalities λ_{i} ≥ 0 for i ≥ 1 we can write

Δb = ∑_{j=0}^{m} λ_{j}q^{−w−j} ≥ λ_{0}q^{−w}.

Putting these inequalities together and using μ_{0} ≤ λ_{0} we obtain

Δl − (Δb + \frac{n − 2}{q − 1} · q^{−w}) < q^{−w−z+1}.

Since we can bound the difference Δl−(Δb+q^{−w}), which we want to prove to be negative, by such a small quantity, we see that we are done if any of μ_{1}, …, μ_{z−1} decreases below q − 1; if any of λ_{1}, …, λ_{z−1} increases above 0; or if the inequality μ_{0} ≤ λ_{0} is strict. So we only have to deal with the case

μ_{1} = ⋯ = μ_{z−1} = n − 2, λ_{1} = ⋯ = λ_{z−1} = 0, and μ_{0} = λ_{0}.

In this case we know that b_{i} = 1 − Δb is close to a multiple p of q^{−w}:

p − q^{−w−z+1} < b_{i} < p.

As in the proof of Lemma 2, Case 2, this means that Lemma 1 can be applied. We use the sequence μ_{1}, …, μ_{z} for the sequence ν_{0}, …, ν_{ℓ} in the statement of Lemma 1 and conclude that the interval [p, p + q^{−w}] is completely covered by intervals of size less than q^{−w}. Consider the λ_{0} intervals if size q^{−w} lying between p and 1: [p, p + q^{−w}], …, [p + (λ_{0} − 1)q^{−w}, p+λ_{0}·q^{−w}]. Among them only λ_{0}−1 intervals are available for the μ_{0} = λ_{0} segments of length q^{−w}. Therefore at least one segment must go into the interval [p − q^{−w}, p], covering b_{i}, a contradiction. This concludes the proof of the first statement of the lemma.

If Δb < 2q^{−w}, then λ_{0} = 1 and we modify the argument as follows. The above upper bound on Δl − Δb = ∑_{j=0}^{∞} μ_{j}q^{−w−j} − ∑_{j=0}^{m} λ_{j}q^{−w−j} was based on the inequalities μ_{0} ≤ λ_{0}, λ_{1} ≥ 0 and μ_{1} ≤ n − 2. (In some cases it was possible that the weaker relation μ_{1} ≤ n − 1 was used.) If we can improve the consequence of these inequalities,

(μ_{0} − λ_{0}) + \frac{μ_{1} − λ_{1}}{q} ≤ \frac{n − 2}{q},

to

(μ_{0} − λ_{0}) + \frac{μ_{1} − λ_{1}}{q} ≤ \frac{q − 1}{q},  (6)

we get an additional term −q^{−w−1}(n − q − 1) in all expressions, and this gives the second bound of the theorem, as the reader may check.

To show the improved inequality (6), consider the possible positions for the μ_{1} segments of length q^{−w−1} in F. There are λ_{1} positions in [b_{i}, 1 − q^{−w}] and q positions in [1 − q^{−w}]. If μ_{0} = λ_{0} = 1, then the interval [1 − q^{−w}] is covered by the one segment of length q^{−w} in F, and this means that the μ_{1} segments of length q^{−w−1} cannot cover all q possible positions in [1 − q^{−w}]. We get μ_{1} ≤ λ_{1} + (q − 1), which gives (6). On the other hand, if μ_{0} = 0 < λ_{0} = 1, then from n ≤ 2q we easily obtain

(μ_{0} − λ_{0}) + \frac{μ_{1} − λ_{1}}{q} ≤ −1 + \frac{n − 1}{q} = \frac{n − 1 − q}{q} ≤ \frac{q − 1}{q}.

THEOREM 1. Let q be an integer with q ≥ 2, and consider a sequence of segments of lengths from the set {q^{−1}, q^{−2}, …}. If their total length is at least

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

then the method of the (q + 1)-st segment ensures an on-line covering of the unit interval. For q ≥ 3 the method of the (q +2)-nd segment guarantees the covering of the unit interval if the total length is at least

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

For q ≥ 4 the method of the (q + 3)-rd segment ensures a covering of the unit interval if the total length is at least

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

For q ≥ 6, the best of all the methods of the n-th segment is the method of the (q + 3)-rd segment. For q = 4 and q = 5, the best method is the method of the (q + 2)-nd segment. For q = 2 and q = 3, the best method is the method of the (q + 1)-st segment.

Proof. We distinguish three cases:

Case 1. We have b_{i} = 0 throughout the algorithm. Then we can use Lemma 3 with Δb = 1 and q^{−w} ≤ 1/q, and a simple calculation shows that for each case Theorem is true.

Case 2. We have lim_{i→∞} b_{i} = 1, for an infinite sequence of segments. During the course of the algorithm, b_{i} increases monotonically, starting at b_{1} = 0. By applying Lemma 2 we see that the total length of segments from amongst τ_{1}S_{1}, …, τ_{i}S_{i} which have non-empty intersection with [0, b_{i}] is less than (1 + \frac{1}{q−1} + \frac{1}{n−1} − \frac{1}{(q−1)(n−1)})b_{i}. It can be checked that this multiplicative factor is less than the number given in the theorem in all cases, and by letting i go to infinity we get a contradiction.

Case 3. We have 0 < b′ < 1, where b′ is either lim_{i→∞} b_{i}, in case of an infinite sequence of segments, or b′ is the value of b_{i} after the given sequence of segments is exhausted. As in Case 3, we can conclude that the total length of segments τ_{1}S_{1}, τ_{2}S_{2}, … which have non-empty intersection with [0, b_{i}] is less than (1 + α)b′, where we define the constant α := \frac{1}{q−1} + \frac{1}{n−1} − \frac{1}{(q−1)(n−1)}. Lemma 3 gives a bound on the sum of lengths of the remaining segments: Let w be the smallest positive integer such that q^{−w} < 1 − b′. This means that b′ ≤ 1 − q^{−w} and q^{−w} ≤ 1/q. If 1 − b′ < 2q^{−w}, Lemma 3 gives the stronger bound (1 − b′) + γq^{−w}, with γ := \frac{n−2}{q−1} − \frac{n−q−1}{q}. Thus the total length of all segments is bounded as follows:

∑_{i} δ_{i} < (1 + α)b′ + (1 − b′) + γq^{−w} = 1 + αb′ + γq^{−w}
≤ α(1 − q^{−w}) + γq^{−w} = 1 + α + q^{−w}(γ − α)
≤ 1 + α + \frac{1}{q}(γ − α) = 1 + \frac{2}{q} + \frac{1}{n − 1} (1 − \frac{2}{q}) + \frac{n − q − 1}{q^{2}(q − 1)}.  (7)

The inequality between the second and third line follows since α ≤ γ.

If 1−b′ ≥ 2q^{−w}, Lemma 3 gives only the weaker bound (1−b′)+γ̃q^{−w} with γ̃ := \frac{n−2}{q−1}, but on the other hand, we can use the stronger inequality b′ ≤ 1 − 2q^{−w}. An analogous chain of relations as above yields

∑_{i} δ_{i} < 1 + α + q^{−w}(γ̃ − 2α).

For n ≥ 5 we can check that γ̃ ≥ 2α, and thus we get

∑_{i} δ_{i} < 1 + α + \frac{1}{q}(γ̃ − 2α) = 1 + \frac{1}{q − 1} · ((1 − \frac{2}{q})(1 + \frac{q − 2}{n − 1}) + \frac{n − 2}{q}). (8)

For n ≤ 4 (and q ≤ n − 1) we have γ̃ ≤ 2α and we therefore get

∑_{i} δ_{i} < 1 + α.  (9)

We must use the weaker of the above two bounds (7) and (8) (or (9), respectively). For n = q + 1 and n = q + 2 this is the bound (7), whereas for n = q + 3 the bound (8) is larger than the bound (7).

The comparison between the different methods for the last part of the theorem is a matter of straightforward computation.

It is possible to construct sequences of segments whose total lengths are arbitrarily close to the bounds of Theorem 1 for which the algorithm does not produce a covering. The constructions are done in the next section. This leads to the conclusion that the three methods considered in our theorem are most effective from all the n-th segment methods.

We remark (although we do not prove it here) that for each n ≥ 2 and q ≥ 2, the method of the n-th segment has performance guarantee similar to Theorem 1, with some finite constant depending on n and q. For instance for q = n we get the performance 1+ \frac{3}{q}. Only the method of the first segment may use an unlimited amount of intervals without producing a covering.

2. Lower-bound examples

We will first construct auxiliary examples of problem instances which cover an interval with density approaching the factor of Lemma 2. Assume that b_{i} is of the form sq^{−w}, where s ∈ {0, …, q^{w} − n − 1}, and that no segment from amongst τ_{1}S_{1}, …, τ_{i−1}S_{i−1} covers a point from (b_{i}, 1]. After the processing the segments of the example, b_{i+t} will be (s + n)q^{−w}, where t denotes the number of segments in the example. Again, no segment from amongst τ_{1}S_{1}, …, τ_{i+t−1}S_{i+t−1} will cover a point from (b_{i+t}, 1]. By the density we mean the ratio Δl/Δb, where Δb = nq^{−w} is the newly covered length and Δl denotes the total length of the t intervals. (This notation is not completely in accordance with Lemma 2, since b_{i} does not jump to b_{i+t} in one step.)

We will construct inductively a sequence of problem instances Ex(1), Ex(2),. . .. The first example Ex(1) just consists of n segments of length q^{−w}. We have Δl = Δb = nq^{−w} and hence the density is ρ_{1} = 1.

Now we describe Ex(k) under the assumption that Ex(k−1) has been defined. Initially we have b_{i} = sq^{−w}. First, we take many small copies of sequences of segments like in Ex(k − 1), but q^{k+2} times smaller, i. e., we take w + k + 2 instead of w. We take as many copies as we can, before b_{i} reaches (s+1)q^{−w}. This means that b_{i} will end up in the interval [(s+1)q^{−w}−nq^{−w−k−2}, (s+1)q^{−w}), which is contained in ((s+1)q^{−w}−q^{−w−k}, (s+1)q^{−w}). This first part, of length greater than q^{−w} − q^{−w−k}, is covered with density ρ_{k}. Next we generate n − 2 segments each of the following lengths: q^{−w−k}, …, q^{−w−1}. None of these segments advance b_{i}. Finally, we put n segments of length q^{−t}, and b_{i} moves up to (s + n)q^{−t}. The total change Δb is (q + 1)q^{−t}. Consequently,

Δl ≥ ρ_{k}(q^{−w} − q^{−w−k}) + (n − 2) ∑_{j=w}^{w+k} q^{−j} + 2q^{−w}

= q^{−w} (ρ_{k} + \frac{(n − 2)q}{q − 1} + 2) − q^{−w−k} (ρ_{k} + \frac{n − 1}{q − 1}) .

Since ρ_{k} ≤ 2 (by Lemma 2), the last expression in parentheses is at most 4, and we get

ρ_{k+1} = \frac{Δl}{Δb} ≥ \frac{ρ_{k} + \frac{(n−2)q}{q−1} + 2}{n} − q^{−k} · \frac{4}{n}.

Since ρ_{k} is increasing, and bounded by Lemma 2, it must converge to some limit. Taking the limit on both sides of the above inequality and solving for ρ = lim_{k→∞} ρ_{k} yields ρ ≥ 1 + \frac{1}{q−1} + \frac{1}{n−1} − \frac{1}{(q−1)(n−1)}. Consequently, the ratio Δl/Δb differs from the factor of Lemma 2 as little as we wish.

The reader may compare the way how this family of examples was constructed with the proof of Lemma 2. In that proof, Case 2 was the “hard case” which made the bound tight. Thus, in our example, this is the case occurring for most of the intervals covered.

We now use these auxiliary examples to construct a sequence of segments of lengths from {q^{−1}, q^{−2}, …} whose total length is arbitrarily close to the bound of Theorem 1 and which does not cover the segment [0, 1] by the method of the n-th segment.

To be specific, we consider only the (q + 2)-nd segment method. In the proof of Theorem 1, equation (7) is the one giving the bound for n = q + 2. This corresponds to the case where the interval [0, (q − 1)/q] is filled according to Lemma 2, and the rest is filled according to Lemma 3.

Applying many times a scaled-down version of the auxiliary example (with q^{−w} sufficiently small), we move the current bottom up to a point strictly between 1 − 1/q − ϵ and 1 − 1/q, where ϵ > 0 is an arbitrary small bound; all the time we take sufficiently large values of k in order to ensure that Δl/Δb is over ρ−ϵ. Then, we find an integer h ≥ 3 such that q^{−h} < ϵ and we add n − 2 = q segments each of the following lengths: q^{−h}, …, q^{−3}. Finally, we add q − 1 segments of length q^{−2}, and one segment of length q^{−1}. The segment [0, 1] is not totally covered (because of a small piece to the left of 1 − 1/q), whereas we have used for the covering a finite sequence of segments of the total length at least

(1 + \frac{1}{q − 1} + \frac{1}{n − 1} − \frac{1}{(q − 1)(n − 1)} − ϵ) (1 − \frac{1}{q} − ϵ) + q ∑_{j=3}^{h} q^{−j} + (q − 1)q^{−2} + q^{−1}.

This total length is arbitrarily close to 1 + \frac{3}{q} − \frac{3q^{2}−4q−1}{q^{4}−q^{2}} if ϵ is chosen sufficiently small.

Analogously we proceed for arbitrary n instead of q + 2. We omit here a tedious calculation which leads to the conclusion where should be the point to which we move the current bottom applying many times the scaled-down version of the auxiliary example. We present only the conclusions.

If n ≥ 2q, then we move the current bottom up to a point strictly between 1 − z/q − ϵ and 1 − z/q, where ϵ > 0 is arbitrarily small; below we explain which integer z should be taken in dependence of the value of n. Denote by m the positive integer fulfilling mq ≤ n − 1 < (m + 1)q. If m ≥ q − 1, then we put z = q − 1. If n = mq + 1 and m < q − 1, we put z = m. If n ≠ mq + 1 and m < q − 1, then we put z = m + 1. In this case the total length of the used segments is arbitrarily close to a number (we omit a complicated formula for it) which is not smaller than 1 + \frac{3}{q} − \frac{2}{q^{2}} .

From now on assume that n < 2q.

If n ≤ \frac{1}{2}(3 + \sqrt{4q − 3}), we move the current bottom up to 1 using only the scaleddown version of the auxiliary example. In this case the total length of the used segments is arbitrarily close to 1 + \frac{1}{n−1} + \frac{1}{q−1}.

If \frac{1}{2}(3 + \sqrt{4q − 3}) < n ≤ q + 2, we move the current bottom up to a point strictly between 1 − 1/q − ϵ and 1 − 1/q, where ϵ > 0 is an arbitrarily small bound. In this case the total length of the used segments can arbitrarily close to 1 + \frac{1}{q} + \frac{q−1}{q(n−1)} + \frac{n−1}{q(q−1)} for

n ≤ q, arbitrarily close to 1 + \frac{3}{q} − \frac{2}{q^{2}} for n = q + 1, and arbitrarily close to 1 + \frac{3}{q} − \frac{3q^{2}−4q−1}{q^{4}−q^{2}} for n = q + 2.

If n ≥ q+3, then we move the current bottom up to a point strictly between 1−2/q−ϵ and 1 − 2/q, where ϵ > 0 is arbitrarily small. In this case the total length of the used segments can be arbitrarily close to 1 + \frac{3}{q} + \frac{q^{2}+n^{2}−2nq−2q−2n+5}{q(q−1)(n−1)}.

The above values lead to the following conclusions about the total length l of the used segments. If q = 2 or q = 3, then l may be arbitrarily close to 1 + \frac{3}{q} − \frac{2}{q^{2}} for n = q + 1, and to a greater number for other n. If q = 3 or q = 4, then l may be arbitrarily close to 1 + \frac{3}{q} − \frac{3q^{2}−4q−1}{q^{4}−q^{2}} for n = q + 2, and to a greater number for other n. If q = 6, then l may be arbitrarily close to 1 + \frac{3}{q} − \frac{4q−8}{q(q−1)(q+2)} for n = q + 3, and to a greater number for other n. If q ≥ 7, then for every n the total length l may be arbitrarily close to a value greater than 1 + \frac{3}{q} − \frac{4q−8}{q(q−1)(q+2)}.

3. Application to covering by cubes

Every cube whose side is of the form 2^{−j}, where j is a positive integer, is called standard. Every 2^{d}-adic covering method of the unit segment induces the following method of covering of the unit cube by standard cubes. Let ϕ_{k} be a bijection between the family of segments of the form [h2^{−dk}, (h + 1)2^{−dk}], where h = 0, …, 2^{dk} − 1, and the family of cubes of the form { (x_{1}, …, x_{d}); h_{i}2^{−k} ≤ x_{i} ≤ (h_{i} + 1)2^{−k} for i = 1, …, d }, where h_{1}, …, h_{d} ∈ {0, …, 2^{k} − 1}. Let ϕ_{k} be given for k = 1, 2, … and let ϕ_{k}(I) ⊂ ϕ_{m}(J) for every segment I of length 2^{−dk} and for every segment J of length 2^{−dm} such that I ⊂ J and k > m. One possibility of such a bijection between the unit interval and the unit cube is a space-filling curve, with its natural parameterization, see Kuperberg [5].

For every standard cube S_{i} we determine a segment of length equal to the side of S_{i} and we use it for the covering of the unit segment according to the given method of covering the unit segment by segments. Simultaneously, we put S_{i} into the place in the unit cube determined by our bijection.

From Theorem 1 we see that this approach permits an on-line covering the unit cube by every sequence of standard cubes of the total volume at least 1 + \frac{3}{q} − \frac{4q−8}{q(q−1)(q+2)} with q = 2^{d}, if d ≥ 3. (For d = 2 we have the constant 1 + 149/240 instead.) This and the fact that every cube Q of side at most 1 contains a standard cube S such that the volume of the cube Q is smaller that 2^{d} times the volume of the cube S imply the following theorem.

THEOREM 2. Every sequence of d-dimensional cubes, where d ≥ 3, of sides at most 1 and of total volume at least

2^{d} + 3 − \frac{4 · 2^{d} − 8}{2^{2d} + 2^{d} − 2}

permits an on-line covering of the unit cube of Euclidean d-space.

For d = 2 the considerations before Theorem 2 lead to the conclusion that every sequence of squares of sides at most 1 and of total area at least 389/60 ≈ 6.483 permits an on-line covering of the unit square in the Euclidean plane. This is a weaker result than that in [4] which gives the estimate \frac{7}{4} · 9^{1/3} + \frac{11}{8} ≈ 5.265. For d ≥ 3 the above theorem improves the estimates given in [3-5].

References

[1] G. Galambos and G.J. Woeginger, On-line bin packing – a restricted survey, Zeitschrift für Operation Research, to appear.

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

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

[4] J. Januszewski and M. Lassak, On-line covering the unit square by squares and the three-dimensional unit cube by cubes, Demonstratio Math. 28 (1995), to appear.

[5] W. Kuperberg, On-line covering a box and the space by cubes, Discrete Comput. Geom. 12 (1994), 83–90.