Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 35 (1994), No. 1, 119-123.

Coating by Cubes

K. Bezdek^{1} and T. Hausel^{1}

Department of Geometry, Eötvös L. University 1088 Budapest, Rákóczi út 5, Hungary

1. Introduction

Let P_{0}, P_{1},…, P_{n} be convex d–polytopes in d–dimensional Euclidean space with pairwise disjoint interiors. We say that P_{0} is coated by P_{1},…, P_{n} if P_{0} ⊂ int( ⋃_{i=0}^{n} P_{i}), where int(·) stands for the interior of the corresponding set. Coating occurs very often in a very natural way. For example, in each tiling every tile is coated by its neighbors. Thus, if we take an arbitrary triangulation of E^{d}, then the number of neighbors of any tile is at least as large as the minimum number of d–simplices that can coat a d–simplex in E^{d}. In this connection the following problem is a rather very basic question.

Problem 1. Find the minimum number of d–simplices that can coat a d–simplex in E^{d}.

The answer to the above question is obviously three in E^{2}. In general, we know only the following.

Proposition. Every d–simplex can be coated by (2d − 1) d–simplices in E^{d}, where d ≥ 2.

Since the number of facets of a d–cube in E^{d} is 2d, the number of d–cubes that can coat a fixed d–cube is at least 2d. The following theorem formulates a sharper statement under some conditions.

Theorem. Let P_{0} be a d–cube of edgelength λ with edges parallel to the coordinate–axes of E^{d}. Moreover, let P_{1},…, P_{n} be a collection of unit d–cubes with edges parallel to the coordinate–axes of E^{d} such that P_{0} is coated by P_{1},…, P_{n}.

(1) If 0 < λ < 1, then n ≥ 2^{d}, where equality can be achieved for any 0 < λ < 1 and d ≥ 1.

(2) If λ = k is a positive integer, then n ≥ 2(k + 1)^{d} − 2k^{d}, where equality can be achieved for any k ≥ 1 and d ≥ 1.

1 The work was partially supported by the Hung. Nat. Foundation for Sci. Research number 326–0413.

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

As a result we get the following:

Corollary. The minimum number of the translates of a d–cube that can coat a given d– cube in E^{d} is at least 2^{d}, where d ≥ 1. If all d-cubes are translates of each other, then 2^{d} can be replaced by 2^{d+1} − 2.

Problem 2. Prove or disprove that the minimum number of d–cubes that can coat a d–cube in E^{d} is 2^{d−1} + 2, where d ≥ 2.

2. Proof of the Proposition

We prove the statement by induction on the dimension d. As the claim is obviously true for d = 2 we may assume that it is true for any d′ < d with d ≥ 3. Thus, let S be a d–simplex in E^{d} with vertices v_{1}, v_{2},…, v_{d+1}. Moreover, let H be the hyperplane in E^{d} spanned by the vertices v_{1}, v_{2},…, v_{d} and let S_{0} be the (d − 1)–simplex with vertices v_{1}, v_{2},…, v_{d}. By induction there are (d − 1)–simplices S_{1}, S_{2},…, S_{2d−3} that coat S_{0} in H. Let v be a point in E^{d} such that v_{d+1} is the relative interior point of the segment v_{1}v and let v′ be a point in E^{d} that is strictly separated from v by H. Then it is easy to see that the d–simplices conv(S_{1} ∪{v}), conv(S_{2} ∪{v}),…, conv(S_{2d−3} ∪{v}), conv{v_{2}, v_{3},…, v_{d+1}, v} and conv(S′_{0} ∪ {v′}) coat the d–simplex S, where S′_{0} is a simplex in H containing S_{0} in its relative interior. This completes the proof of the Proposition.

3. Proof of the Theorem

Proof of (1). In the following proof we assume only that the edgelengths of the d–cubes P_{1},…, P_{n} are larger than λ.

At first, remove the d–cubes of the collection P_{1},…, P_{n} that are disjoint from P_{0}. Let P_{1},…, P_{n} denote the system left. Obviously, P_{1},…, P_{n} still coat P_{0}. We are going to show that n = 2^{d}. Recall that an orthant in E^{d} is the closure of a connected component of the complement of d pairwise orthogonal hyperplanes of E^{d}.

Lemma 1. Each d–cube P_{i}, 1 ≤ i ≤ n can be replaced by an orthant O_{i} with P_{i} ⊂ O_{i} such that the edges of the orthants O_{1},…, O_{n} are parallel to the coordinate–axes of E^{d} and the interiors of the orthants O_{1},…, O_{n} are pairwise disjoint.

Proof. Take a d cube P_{i}, 1 ≤ i ≤ n. Let v_{i} be the vertex of P_{i} that lies closest to the d–cube P_{0}. Then let O_{i} be the orthant with apex v_{i} and with edges parallel to the coordinate–axes of E^{d} and with P_{i} ⊂ O_{i}. We are going to show that each O_{i} is disjoint from the interiors of the d–cubes P_{1},…, P_{i−1}, P_{i+1},…, P_{n} and then we prove that the interiors of the orthants O_{1},…, O_{n} are pairwise disjoint indeed. In order to do so we need the following:

Lemma 2. Let H be the hyperplane of any facet of P_{i} that does not contain v_{i}. Then H ∩ P_{0} = ∅.

Proof. (Indirect) Assume that H ∩ P_{0} ≠ ∅. Then take the orthogonal projection of v_{i} onto H. This is a vertex say v′_{i} of P_{i}. Moreover, let w_{i} be the point of P_{0} that is closest to v_{i} and let w′_{i} be the orthogonal projection of w_{i} onto H. Obviously, as H ∩ P_{0} ≠ ∅ we have w′_{i} ∈ P_{0}. Finally, as the edgelength of P_{0} is smaller than the edgelength of P_{i} we get that dist(v_{i}, w_{i}) > dist(v′_{i}, w′_{i}). Thus, dist(v_{i}, P_{0}) > dist(v′_{i}, P_{0}), a contradiction.

Now imagine a d–cube P_{j}, j ≠ i with int P_{j} ∩ int O_{i} ≠ ∅. Recall that int P_{j} ∩ int P_{i} = ∅. Then obviously, there exists a facet of P_{i} the hyperplane H of which separates int P_{j} from int P_{i}. As int P_{j} ∩ int O_{i} ≠ ∅ therefore v_{i} ∉ H. Hence, Lemma 2 implies that H ∩P_{0} = ∅. Now, recall that P_{i} ∩P_{0} ≠ ∅ and P_{j} ∩P_{0} ≠ ∅. Consequently, H (that separates P_{i} from P_{j}) must intersect (the convex set) P_{0}, a contradiction. Hence, we proved that int O_{i} ∩ int P_{j} = ∅ for any i ≠ j ∈ {1,…, n}. In order to finish the proof of Lemma 1 we proceed as follows. Take O_{1} and enlarge P_{1} from v_{1} by a very large factor obtaining the cube P′_{1} the vertex v_{1} of which is still the closest vertex to P_{0}. As a result of the previous arguments P′_{1}, P_{2},…, P_{n} coat P_{0}. Then enlarge P_{2}, P_{3},…, P_{n} after each other in order to get a coating system of P_{0} using rather large d–cubes. Keep doing this to see that the orthants O_{1},…, O_{n} have pairwise disjoint interiors. This completes the proof of Lemma 1.

Apply Lemma 1 to get a system {O_{1},…, O_{n}} of orthants with P_{i} ⊂ O_{i} and with edges parallel to the coordinate–axes of E^{d} such that the orthants O_{1},…, O_{n} have pairwise disjoint interiors, where 1 ≤ i ≤ n. Obviously, no two of the orthants O_{1},…, O_{n} are translates of each other and they coat P_{0}. Thus, n ≤ 2^{d}. Take the 2^{d} − 1 orthants with edges parallel to the coordinate–axes of E^{d} that share the same vertex of P_{0} as an apex and are disjoint from the interior of P_{0}. Then it is easy to see that any O_{i} intersects the interior of 2^{l} orthants out of 2^{d} −1. Hence, there must be an O_{i} that intersects the interior of one orthant out of 2^{d} − 1 implying that its apex v_{i} is a vertex of P_{0}. Thus, n ≥ 2^{d} and so n = 2^{d}.

We are left with the proof of showing the existence of 2^{d} orthants O_{1},…, O_{2^{d}} that coat P_{0}. As a result of the previous arguments we look for 2^{d} orthants with the property that the apex of each orthant is a vertex of P_{0} and each vertex of P_{0} is an apex of exactly one orthant. We prove the existence of such orthants by induction on the dimension d. They obviously exist in case d = 2. So assume that if P′_{0} is a (d − 1)–cube of edgelength λ with edges parallel to the coordinate–axes of E^{d−1}, then there are 2^{d−1} orthants in E^{d−1} say, O′_{1},…, O′_{2^{d−1}} that coat P′_{0} in E^{d−1}. Also, assume that E^{d−1} is a hyperplane of E^{d}. Then for each orthant O′_{i}, 1 ≤ i ≤ 2^{d−1} in E^{d−1} we assign two orthants of E^{d} say, +O_{i} and −O_{i} such that the distinct orthants +O_{i} and −O_{i} share the (d − 1)–dimensional orthant O′_{i} as a facet in common. Let F′_{1} and F′_{2} be two opposite (i.e., disjoint) facets of P′_{0}. Without loss of generality we may assume that the apexes of the orthants O′_{1},…, O′_{2^{d−2}} belong to F′_{1} and the apexes of the orthants O′_{2^{d−2}+1},…, O′_{2^{d−1}} belong to F′_{2}. Finally, let e_{1} be the vector of length λ with e_{1} + F′_{1} = F′_{2} and let e_{d} be a vector of length λ orthogonal to E^{d−1}. Without loss of generality we may assume that the d–dimensional orthants +O_{1},…, +O_{2^{d−1}} lie in that closed half–space of E^{d} bounded by the E^{d−1} into which e_{d} points.

Then take the following 2^{d} orthants in E^{d}:

e_{d} + (−O_{1}), e_{d} + (−O_{2}),…, e_{d} + (−O_{2^{d−2}});
e_{1} + e_{d} + (+O_{1}), e_{1} + e_{d} + (+O_{2}),…, e_{1} + e_{d} + (+O_{2^{d−2}});
− e_{1} + (−O_{2^{d−2}+1}), −e_{1} + (−O_{2^{d−2}+2}),…, −e_{1} + (−O_{2^{d−1}});

+O_{2^{d−2}+1}, +O_{2^{d−2}+2},…, +O_{2^{d−1}}.

If P_{0} is the d–cube conv(P′_{0} ∪ (e_{d} + P′_{0})), then using the induction hypothesis that P′_{0} is coated by the (d − 1)–dimensional orthants O′_{1},…, 0′_{2^{d−1}} in E^{d−1} it is easy to see that the above 2^{d} d–dimensional orthants coat P_{0} in E^{d}. This completes the proof of (1).

Proof of (2). At first, we show that if P_{0} has an integer edgelength say k ≥ 1, then P_{0} can be coated by 2(k + 1)^{d} − 2k^{d} unit d–cubes with edges parallel to the coordinate axes of E^{d}, i.e., parallel to the edges of P_{0}. We prove this by induction on the dimension d. The claim is obviously true for the case d = 1. So assume that it is true for every d′ < d and take a d–cube P_{0} of E^{d} with integer edgelength k ≥ 1. Let H_{0} be a supporting hyperplane of P_{0} that intersects P_{0} in a facet F_{0}. Then let H_{l} be the translate of H_{0} by the vector of length l orthogonal to H_{0} that intersects P_{0} in a (d−1)–cube F_{l} = H_{l} ∩ P_{0} of edgelength k, where l = 1,…, k. By induction each F_{l} can be coated by 2(k + 1)^{d−1} − 2k^{d−1} unit (d − 1)–cubes in H_{l}, where l = 0, 1,…, k. Thus, if we place k(2(k +1)^{d−1} −2k^{d−1}) unit d–cubes between the consecutive hyperplanes H_{i}, H_{i+1}, 0 ≤ i ≤ k − 1 properly, then we are left with the problem to coat P_{0} along the facets F_{0} and F_{k} only. This can be done easily by 2(k +1)^{d−1} unit d–cubes. Thus, P_{0} is coated by k(2(k +1)^{d−1} −2k^{d−1})+2(k +1)^{d−1} = 2(k +1)^{d} −2k^{d} unit d–cubes in E^{d} finishing the construction.

At second, notice that each unit d–cube of the above construction has a (d − 1)– dimensional intersection with P_{0}. The following easy lemma is the key to prove the claim (2) completely.

Lemma 3. Let P_{0} be a d–cube of E^{d} with integer vertices and with edges parallel to the coordinate–axes of E^{d}. We assign to P_{0} each orthant of E^{d} that has an integer apex belonging to P_{0} and the edges of which are parallel to the coordinate–axes of E^{d} such that the interior of the orthant is disjoint from P_{0}. If P is a unit d–cube of E^{d} with edges parallel to the coordinate–axes of E^{d} such that P ∩ P_{0} is (d − 1)–dimensional, then the number of the orthants assigned to P_{0}, each of whose interior intersects P and each of whose apex belongs to P, is always 2^{d−1}.

Proof. We leave the rather easy proof to the reader.

To complete the proof of (2) assume that P_{0} is coated by the unit d–cubes P_{1},…, P_{n} in E^{d}. Without loss of generality we may assume that P_{0} is a d–cube of E^{d} with integer vertices and with edges parallel to the coordinate–axes of E^{d}. Assign to P_{0} all orthants described in Lemma 3. As P_{i} ∩ P_{0} is at most (d − 1)–dimensional (1 ≤ i ≤ n) it is easy to see (using Lemma 3) that the number of the orthants assigned to P_{0} the interior of each of which intersects P_{i} and the apex of each of which belongs to P_{i} is at most 2^{k−1}. Thus, a very simple counting argument implies that n is at least as large as the number of unit d–cubes in the above construction, i.e., 2(k + 1)^{d} − 2k^{d}. This completes the proof of (2).

4. Proof of the Corollary

Without loss of generality we may assume that P_{0} is a d–cube of edge length λ with edges parallel to the coordinate–axes of E^{d} such that it is coated by the unit d–cubes P_{1},…, P_{n} of E^{d} the edges of which are par allel to the coordinate–axes of E^{d}. If λ ≤ 1, then the claim follows from the Theorem in a straight way. So, we are left with the case, when λ > 1. Then take two opposite facets say, F and F′ of P_{0}. Obviously, F (F′, resp.) is a (d − 1)– cube of edge length λ that is covered by some d–cubes of the collection P_{1},…, P_{n} each of which has edge length smaller than λ. Thus, the number of d–cubes of the collection P_{1},…, P_{n} that cover F (F′, resp.) is obviously at least 2^{d−1}. Hence, n ≥ 2^{d−1}+2^{d−1} = 2^{d}.

Acknowledgement. We are indebted to the referee for the valuable remarks which made the presentation more clear.

Received 14.10.93