Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 42 (2001), No. 2, 313-324.

Covering Belt Bodies by Smaller Homothetical Copies

Vladimir Boltyanski^{1} Horst Martini

CIMAT, A.P. 402, 36000 Guanajuato, Gto., Mexico Fakultät für Mathematik, Technische Universität Chemnitz D-09107 Chemnitz, Germany

Abstract. Let b(K) denote the minimal number of smaller homothetical copies of a convex body K ⊂ ℝ^{n}, n ≥ 2, covering K. For the class B of belt bodies, which is dense in the set of all convex bodies (in the Hausdorff metric), 3 · 2^{n−2} is known to be an upper bound on b(K) if K is different from a parallelotope. We will show that (except for all parallelotopes and two particular cases, each satisfying b(K) = 3 · 2^{n−2}) within B this bound can be improved to 5 · 2^{n−3}. Keywords: belt body, belt polytope, Hadwiger’s covering problem, homothetical copy, (outer) illumination, zonoid, zonotope.

1. Introduction

Let ℝ^{n}, n ≥ 2, denote the n-dimensional Euclidean space. A compact, convex set K ⊂ ℝ^{n} with nonempty interior is said to be a convex body. As usual, we will use the common abbreviations dim, int, cl, bd and vert for dimension, interior, closure, boundary, and vertex set, respectively. We write b(K) for the minimal positive integer k such that K can be covered by k of its smaller homothetical copies. A famous open problem (which was posed in geometrically different, but equivalent forms by F. W. Levi, H. Hadwiger, I. Gohberg and A. Markus, cf. [16], [13], and [11]) asks whether b(K) ≤ 2^{n} for each convex body K ⊂ ℝ^{n}, with equality if and only if K is parallelotope. We remark that in [16] and [11] this problem was positively answered for n = 2 (the paper [11] was written in 1956 but, due to some events in Russia, published much later, see also [6]). For n ≥ 3 the problem is still unsolved. Thus it is interesting to solve it for sufficiently large subclasses of the class of convex bodies. One of the most striking results in this direction is M. Lassak’s positive solution b(M) ≤ 8 for any centrally symmetric, three-dimensional convex body M, cf. [15]. In this article we consider the problem for the family of belt bodies which was introduced in [1] and [5] (for a definition, see below).

1Research supported by Deutsche Forschungsgemeinschaft 0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2001 Heldermann Verlag

We also refer to Section 34 of [8] and to [18] for almost complete surveys regarding these and related results.

In 1960, V. Boltyanski [4] formulated the illumination problem for convex bodies. A boundary point x of a convex body K ⊂ ℝ^{n} is illuminated by the direction defined by a nonzero vector e if x+λe ∈ int K for a sufficiently small λ > 0. The illumination problem asks for the minimal positive integer k such that there are k directions in ℝ^{n} which illuminate the whole boundary of K (i.e., each boundary point is illuminated by at least one of the considered directions). Denote this minimal number by c(K). In [4], the equality b(K) = c(K) for each convex body K ⊂ ℝ^{n} was established. From our point of view, the illumination arguments yield a more convenient and more intuitive method than the consideration of coverings by smaller homothetical copies. Thus in the sequel we will use the terminology of illumination and the number c(K) instead of b(K).

For formulating some lemmas, we recall that an n-dimensional polytope Z ⊂ ℝ^{n} is said to be a zonotope if it is representable as the vector sum of a finite set of line segments: Z = I_{1} + ⋯ + I_{r}, r ≥ n. Furthermore, a convex body V ⊂ ℝ^{n} is a zonoid if it is the limit of a convergent sequence of zonotopes (in the Hausdorff metric). Another generalization of the notion of zonotopes is that of belt polytopes. A convex n-dimensional polytope B ⊂ ℝ^{n} is called a belt polytope if it has a non-degenerate segment summand parallel to each of its edges. In other words, each belt polytope B is representable in the form B = Z + B′, where Z is a zonotope such that each of its edges is parallel to an edge of Z. (It should be noticed that sometimes belt polytopes were also called planets, see, e.g., [3] and [17].)

It seems to be natural to define belt bodies as the limits of convergent sequences of belt polytopes. But this is incorrect since every convex body can be represented as such a limit; cf. [7] and Section 41 of [8]. In this connection, the class of belt bodies is defined in a more delicate way, namely: Let H(K) denote the set of all outward normal unit vectors of a convex body K ⊂ ℝ^{n} at its regular boundary points. A nonzero vector e is said to be a belt vector of K if for each supporting line L of K, parallel to e, and for a ∈ L ∩ K at least one of the rays defined on L by a is a tangential ray of K at a. A convex body K ⊂ ℝ^{n} is said to be a belt body if for every q ∈ H(K) and any ε > 0 there exist linearly independent belt vectors e_{1}, …, e_{n−1} of K such that the hyperplane spanned by them has a unit normal vector p satisfying ||p − q|| < ε. Each zonotope, each zonoid, and each belt polytope is a belt body, see Sections 40 and 41 of [8]. And it is clear that, as already the set of belt polytopes, also the family of belt bodies is dense in the set of all compact, convex bodies (with respect to the Hausdorff metric).

In 1985, H. Martini [17] confirmed the conjecture c(K) ≤ 2^{n} for the class of belt polytopes in the following reinforced form: If an n-dimensional belt polytope P is not a parallelotope, then c(P) ≤ 3 · 2^{n−2}. In 1992, V. Boltyanski and P. Soltan [9] established the same result for the class of zonoids. And in 1996, V. Boltyanski [5] confirmed this result for belt bodies: c(B) ≤ 3 · 2^{n−2} for any n-dimensional belt body B distinct from a parallelotope, see also [7].

In this article, we give a complete list of the n-dimensional belt bodies with c(B) = 3 · 2^{n−2}, and we prove that for all other n-dimensional belt bodies the more exact estimate c(B) ≤ 5 · 2^{n−3} holds.

2. Results

For the complete list referring to c(B) = 3 · 2^{n−2} we need the following

Definition 1. Let I_{1}, I_{2}, I_{3}, I_{4} be four line segments in ℝ^{3} each three of which are in general position (i.e., not parallel to a plane). The zonotope D = I_{1} + I_{2} + I_{3} + I_{4} is said to be a parallelogramic dodecahedron.

Remark 1. In the particular case when all segments I_{1}, I_{2}, I_{3}, I_{4} have the same length, such a zonotope is named a rhombic dodecahedron, since then all its facets are rhombs. Very often this specified notion is incorrectly used for the general case, described by Definition 1, where the facets of D can be parallelograms with different side lengths. Nevertheless, also the restricted class of rhombic dodecahedra is interesting in itself. For example, S. Bilinski [2] surprisingly found that, besides the classical rhombic dodecahedron (which is a Catalan solid and dual to the Archimedean cuboctahedron), there exists a second type of rhombic dodecahedra all of whose rhombic facets are congruent, see also [10], p. 156, for a nice approach.

Remark 2. It is easy to see that each parallelogramic dodecahedron D has six 4-valent vertices (and eight 3-valent ones), and that no two of these 4-valent vertices can be illuminated by the same direction, since each such pair of vertices is antipodal (i.e., the two vertices belong to a pair of parallel facets of D). Thus we have c(D) = 6, see also [17].

Now we are ready to formulate our

Theorem. Let B ⊂ ℝ^{n} be an n-dimensional belt body (in particular, a zonoid or a zonotope), where n ≥ 3. Then c(B) ≤ 5 · 2^{n−3}, except for the following three particular cases:

(i) B is an n-dimensional parallelotope (= affine cube); in this case c(B) = 2^{n}. (ii) B is the direct vector sum of a 2-dimensional belt body C distinct from a parallelogram

and an (n − 2)-dimensional parallelotope (i.e., B is an (n − 2)-fold prism over C); in this case c(B) = 3 · 2^{n−2}.

(iii) B is the direct vector sum of a 3-dimensional parallelogramic dodecahedron Z and an (n − 3)-dimensional parallelotope (i.e., it is an (n − 3)-fold prism over Z); in this case c(B) = 3 · 2^{n−2}.

The proof of this theorem is based on several lemmas which are possibly interesting for themselves. To formulate them, we recall that an n-dimensional zonotope Z is said to be indecomposable if there is no representation Z = Z_{1}⊕⋯⊕Z_{r} with r ≥ 2 and dim Z_{i} ≥ 1, i = 1, …, r, where ⊕ means direct vector sum.

Lemma 1. Let Z be a 3-dimensional, indecomposable zonotope which is representable as the vector sum of at least 5 pairwise non-parallel line segments. Then c(Z) ≤ 5.

Lemma 2. Let Z be a 4-dimensional, indecomposable zonotope which is representable as the vector sum of 5 pairwise non-parallel line segments. Then c(Z) = 10.

Lemma 3. Let Z be an n-dimensional, indecomposable zonotope, n ≥ 4. Then c(Z) ≤ 5 · 2^{n−3}.

The following lemma affirms that our Theorem is valid for the family of all zonotopes.

Lemma 4. For any n-dimensional zonotope Z, n ≥ 3, which is distinct from the three particular cases in the Theorem, the inequality c(Z) ≤ 5 · 2^{n−3} holds.

To extend this result from zonotopes to arbitrary belt bodies, we have to generalize the notion of tangential zonotopes, introduced for zonoids in [9], to general belt bodies.

Definition 2. Let B ⊂ ℝ^{n} be a belt body, e_{1}, …, e_{k} be some of its belt vectors, and I_{1}, …, I_{k} be line segments parallel to the vectors e_{1}, …, e_{k}, respectively. Then the zonotope Z = I_{1} + ⋯ + I_{k} is said to be a tangential zonotope of the belt body B. Moreover, a belt polytope P with the property that each of its edges is parallel to one of the vectors e_{1}, …, e_{k} is called a tangential belt polytope of B.

Remark 3. It is possible to prove the following Approximation Theorem: For every belt body B ⊂ ℝ^{n} there exists a sequence P_{1}, P_{2}, … of its tangential belt polytopes such that lim_{k⟶∞} P_{k} = B (in the sense of the Hausdorff metric). In other words, for every real number ε > 0 there exists a tangential belt polytope P of B such that the Hausdorff distance d(P, B) is less than ε. In [9], the Approximation Theorem was used in the proof of the analogue (for zonoids) of Lemmas 5 and 7 below, and this allowed to establish that for every n-dimensional zonoid Z distinct from a parallelotope the inequality c(Z) ≤ 3 · 2^{n−2} holds. Here we give another, more simple proof of Lemmas 5 and 7 below (for all belt bodies), and by this we do not need the Approximation Theorem.

Lemma 5. For any n-dimensional belt body B ⊂ ℝ^{n} and each of its n-dimensional, tangential zonotopes (or its tangential belt polytopes) Z, the inequality c(B) ≤ c(Z) holds.

Lemma 6. Let B ⊂ ℝ^{n} be an n-dimensional belt body having only n+1 belt directions defined by vectors e_{1}, …, e_{n}, e_{n+1}, where e_{1}, …, e_{n} are linearly independent and e_{n+1} = λ_{1}e_{1} + ⋯ + λ_{n}e_{n} with some nonzero coefficients. Then B is a zonotope that is the vector sum of line segments I_{1}, …, I_{n}, I_{n+1} parallel to the vectors e_{1}, …, e_{n}, e_{n+1}, respectively.

Remark 4. Let W_{n} ⊂ ℝ^{n} be a zonotope as in Lemma 6. It is easily shown (by a method as in the proof of Lemma 3, see below) that the inequalities

\frac{c(W_{2})}{2^{2}} ≤ \frac{c(W_{3})}{2^{3}} ≤ \frac{c(W_{4})}{2^{4}} ≤ ⋯ ≤ \frac{c(W_{k})}{2^{k}} ≤ ⋯

hold. The first and the second fraction in this sequence are equal to the number \frac{3}{4}, whereas the third fraction is equal to \frac{5}{8} (due to Lemma 2). Evaluating fractions after the third one, one might obtain estimates more precise than those in our Theorem.

Lemma 7. Let M ⊂ ℝ^{n} be an n-dimensional belt body. If M is indecomposable, then there exists an n-dimensional, indecomposable, tangential zonotope Z of the body M.

3. Proofs

Proof of Lemma 1. The normal fans of n-dimensional zonotopes are hyperplane arrangements in projective (n−1)-spaces (see, e.g., Chapter 7 in [19]). Therefore these arrangements can be used to study the combinatorial types of zonotopes. Thus the complete list of combinatorial types of 3-zonotopes which are vector sums of 5 pairwise non-parallel segments can be taken from Figures 18.1.1 and 18.1.2 of [12], where all projective 2-arrangements of 5 lines are presented. Except for the decomposable case of the octagonal prism, there are three types shown in the figure below. Now it is possible to show that the whole boundary of every such 3-zonotope Z can be illuminated by 5 directions.

For every polytope Z it suffices to illuminate (instead of bd Z) the set vert Z. Furthermore, it is easy to see that a subset M of vert Z can be illuminated by one direction if M can be described in the following way. Consider a zone Q (or, in other terms, a belt) of Z, i.e., the union of all edges of Z parallel to each other and all segments in bd Z parallel to these edges. Let e ≠ o be a vector parallel to the edges of the zone Q. Denote by C_{1}, C_{2} two open caps forming together (bd Z)\Q, where C_{1} is the cap completely illuminated by e. Let p : ℝ^{3} ⟶ L be the projection on a plane L in the direction of e. Choose some vertices w_{1}, …, w_{k} from (cl C_{1})∩Q such that the vertices p(w_{1}), …, p(w_{k}) of the polygon p(Z) can be illuminated in L by one direction. Then by a small perturbation of e we can obtain a vector whose direction illuminates the vertices w_{1}, …, w_{k} ∈ Z and all vertices from C_{1}. Having this in mind, we can descriptively prove that each of the 3-zonotopes shown in the figure can be illuminated by 5 directions. Namely, in every partial figure the set vert Z can be dissected into 5 disjoint subsets (with an own marking, in every case) each of which can be illuminated by one direction.

Thus Lemma 1 is verified for all indecomposable 3-zonotopes with 5 zones. And by Theorem 34.8 from [8] this result can be extended to all indecomposable 3-zonotopes with a larger number of zones. □

Also we remark that, e.g., in the third picture of the figure one can easily find five vertices being pairwise antipodal. Hence there are no four directions illuminating all the vertices of this zonotope.

Proof of Lemma 2. Let Z be the 4-dimensional, indecomposable zonotope which is the vector sum of pairwise non-parallel segments I_{1}, I_{2}, I_{3}, I_{4}, I_{5}. Denote by e_{i} the vector going from the midpoint of the segment I_{i} (as starting point) to one of its endpoints, i ∈ {1, 2, 3, 4, 5}. Then every four of the vectors e_{1}, e_{2}, e_{3}, e_{4}, e_{5} are linearly independent (otherwise Z is decomposable). Changing the orientation of the vectors, if necessary, we can assume that

λ_{1}e_{1} + λ_{2}e_{2} + λ_{3}e_{3} + λ_{4}e_{4} + λ_{5}e_{5} = o

with positive coefficients λ_{1}, λ_{2}, λ_{3}, λ_{4}, λ_{5}. Denote the vector λ_{i}e_{i} by v_{i}, i ∈ {1, 2, 3, 4, 5}. Then v_{1} + v_{2} + v_{3} + v_{4} + v_{5} = o, and every four of the vectors v_{1}, v_{2}, v_{3}, v_{4}, v_{5} are linearly independent. Furthermore, denote by W the zonotope that is the set of all points

μ_{1}v_{1} + μ_{2}v_{2} + μ_{3}v_{3} + μ_{4}v_{4} + μ_{5}v_{5}

with |μ_{i}| ≤ 1, i ∈ {1, 2, 3, 4, 5}. The zonotopes Z and W have pairwise parallel edges. Consequently c(Z) = c(W). Thus we have to prove that c(W) = 10.

The vertices of W are the points ±w_{i} and ±w_{i,j}, where w_{i} = 2v_{i} and w_{i,j} = 2(v_{i} + v_{j}); here i, j ∈ {1, 2, 3, 4, 5} with i ≠ j. For example, w_{1} = 2v_{1} = v_{1} − v_{2} − v_{3} − v_{4} − v_{5}, since v_{1} + v_{2} + v_{3} + v_{4} + v_{5} = o. It is easy to show that the vector q_{1} = −v_{1} − εv_{2} − ε^{2}v_{4} with 0 < ε < \frac{1}{2} illuminates the vertices

\begin{aligned}w_{1} & = & v_{1} − v_{2} − v_{3} − v_{4} − v_{5}, \\ w_{1,2} & = & v_{1} + v_{2} − v_{3} − v_{4} − v_{5}, \\ −w_{3,5} & = & v_{1} + v_{2} − v_{3} + v_{4} − v_{5} . \end{aligned}

Indeed, the points

w_{1} + q_{1} = w_{1} + q_{1} + \frac{3}{2}ε(v_{1} + v_{2} + v_{3} + v_{4} + v_{5}) =
\frac{3}{2}εv_{1} + (−1 + \frac{1}{2}ε) v_{2} + (−1 + \frac{3}{2}ε) (v_{3} + v_{5}) + (−1 + ε (\frac{3}{2} − ε)) v_{4} ,
w_{1,2} + q_{1} = w_{1,2} + q_{1} + \frac{1}{2}ε(v_{1} + v_{2} + v_{3} + v_{4} + v_{5}) =
\frac{1}{2}εv_{1} + (1 − \frac{1}{2}ε) v_{2} + (−1 + \frac{1}{2}ε) (v_{3} + v_{5}) + (−1 + ε (\frac{1}{2} − ε)) v_{4} ,
−w_{3,5} + q_{1} = −w_{3,5} + q_{1} + \frac{1}{2}ε^{2}(v_{1} + v_{2} + v_{3} + v_{4} + v_{5}) =
\frac{1}{2}ε^{2}v_{1} + (1 − ε (1 − \frac{1}{2}ε)) v_{2} + (−1 + \frac{1}{2}ε^{2}) (v_{3} + v_{5}) + (1 − \frac{1}{2}ε^{2}) v_{4}

are situated in the interior of the zonotope W (since all coefficients on the right-hand side are strictly contained between −1 and 1).

Shifting all indices by 1, we obtain successively that

the vector q_{2} = −v_{2} − εv_{3} − ε^{2}v_{5} illuminates the vertices w_{2}, w_{2,3}, −w_{4,1}, the vector q_{3} = −v_{3} − εv_{4} − ε^{2}v_{1} illuminates the vertices w_{3}, w_{3,4}, −w_{5,2}, the vector q_{4} = −v_{4} − εv_{5} − ε^{2}v_{2} illuminates the vertices w_{4}, w_{4,5}, −w_{1,3}, the vector q_{5} = −v_{5} − εv_{1} − ε^{2}v_{3} illuminates the vertices w_{5}, w_{5,1}, −w_{2,4}.

It follows that the vectors ±q_{1}, ±q_{2}, ±q_{3}, ±q_{4}, ±q_{5} illuminate all vertices of W, i.e., c(W) ≤ 10.

Now we prove the opposite inequality. Consider the coordinate system x_{1}, x_{2}, x_{3}, x_{4} in ℝ^{4} that has v_{1}, v_{2}, v_{3}, v_{4} as unit coordinate vectors (recall that every 4 of the vectors v_{1}, v_{2}, v_{3}, v_{4}, v_{5} are linearly independent). Then some 15 vertices of W have the following coordinates.

w_{1} = (2, 0, 0, 0), w_{2} = (0, 2, 0, 0), w_{3} = (0, 0, 2, 0) ,
w_{4} = (0, 0, 0, 2), −w_{5} = (2, 2, 2, 2) ;
w_{1,2} = (2, 2, 0, 0), w_{1,3} = (2, 0, 2, 0), w_{1,4} = (2, 0, 0, 2) ,
w_{2,3} = (0, 2, 2, 0), w_{2,4} = (0, 2, 0, 2), w_{3,4} = (0, 0, 2, 2) ,
−w_{1,5} = (0, 2, 2, 2), −w_{2,5} = (2, 0, 2, 2) ,
−w_{3,5} = (2, 2, 0, 2), −w_{4,5} = (2, 2, 2, 0) .

We call these vertices positive. Other vertices (negative ones) are symmetric to the positive vertices with respect to the origin (i.e., have the same coordinates with minus sign).

Now it is easy to show the following: The hyperplanes in ℝ^{4} described in the considered coordinate system x_{1}, x_{2}, x_{3}, x_{4} by the equations x_{i} = 2, x_{i} = −2, x_{i} − x_{j} = 2 with i, j ∈ {1, 2, 3, 4}, i ≠ j, are supporting hyperplanes of W.

To finish the proof, it is sufficient to establish that no more than two of the 20 vertices ±w_{i,j} can be illuminated simultaneously by any direction. Indeed, choose any three distinct vertices from the 20 vertices ±w_{i,j}. We consider two mutually exclusive cases: a) There are two positive and one negative vertices among the three chosen ones (or two negative and one positive, the proof in this case being analogous). There are not less than three coordinates which are equal to 2 for at least one chosen positive vertex. Consequently there is a coordinate x_{i} which is equal to −2 for the chosen negative vertex w^{(−)} and which is equal to 2 for a positive vertex (denote it by w^{(+)}). This means that w^{(+)} and w^{(−)} are situated in the parallel supporting hyperplanes x_{i} = 2 and x_{i} = −2. Consequently they cannot be illuminated simultaneously by any direction.

b) All three chosen vertices are positive (or all three are negative, the proof in this case being analogous). Then it is possible to select two vertices w^{(1)}, w^{(2)} from the three chosen ones and two distinct indices i, j ∈ {1, 2, 3, 4} such that x_{i} = 2, x_{j} = 0 for w^{(1)} and x_{i} = 0, x_{j} = 2 for w^{(2)}. Indeed, this assertion is evident if there are not less than two positive 3-vertices (i.e., with three coordinates equal to 2). Even if there is no more than one positive 3-vertex among the three chosen vertices, then there are two positive 2-vertices (with two coordinates equal to 2), and the above assertion holds, too. This means that w^{(1)} and w^{(2)} are situated in the parallel supporting hyperplanes x_{i} −x_{j} = 2 and x_{j} −x_{i} = 2 of W, respectively. Consequently, they cannot be illuminated simultaneously by any direction. □

Proof of Lemma 3. Let Z = I_{1}+⋯+I_{k}, where I_{1}, …, I_{k} are pairwise nonparallel segments. Denote by e_{1}, …, e_{k} the unit vectors parallel to I_{1}, …, I_{k}, respectively. Since dim Z = n, we have k > n and there are n linearly independent vectors among e_{1}, …, e_{k}. Assume that e_{1}, …, e_{n} is a linarly independent n-tuple. Then every vector from {e_{n+1}, …, e_{k}} is a linear combination of e_{1}, …, e_{n}, and in each case at least two coefficients are nonzero (since e_{1}, …, e_{k} are pairwise nonparallel). We consider now three possible cases. Case 1) Among e_{n+1}, …, e_{k}, there is a vector that is a linear combination of e_{1}, …, e_{n} with at least 4 nonzero coefficients. Let, e.g.,

e_{n+1} = λ_{1}e_{1} + ⋯ + λ_{n}e_{n} ,

where λ_{1}, λ_{2}, λ_{3}, λ_{4} are nonzero. Denote by q the composition of the projections parallel to e_{5}, …, e_{n}. Then q(Z) is a 4-dimensional zonotope, and c(Z) ≤ c(q(Z))·2^{n−4} (by Theorem 42.7 from [8]). Furthermore, q(Z) is the vector sum of the segments I′_{1} = q(I_{1}), I′_{2} = q(I_{2}), I′_{3} = q(I_{3}), I′_{4} = q(I_{4}), I′_{n+1} = q(I_{n+1}), …, I′_{k} = q(I_{k}), i.e., q(Z) = Z′ + Z′′ with

Z′ = I′_{1} + ⋯ + I′_{4} + I′_{n+1}, Z′′ = I′_{n+2} + ⋯ + I′_{k} .

Since c(q(Z)) ≤ c(Z′) (cf. Theorem 34.8 in [8]), it is sufficient to prove that c(Z′) = 10. Indeed, the segments I′_{1}, I′_{2}, I′_{3}, I′_{4}, I′_{n+1} are parallel to the vectors e′_{1} = q(e_{1}), e′_{2} = q(e_{2}), e′_{3} = q(e_{3}), e′_{4} = q(e_{4}), e′_{n+1} = q(e_{n+1}), and we have e′_{n+1} = λ_{1}e′_{1} + λ_{2}e′_{2} + λ_{3}e′_{3} + λ_{4}e′_{4}. By Lemma 2, c(Z′) = 10. Case 2) None of the vectors e_{n+1}, …, e_{k} is a linear combination of four (or more) of the vectors e_{1}, …, e_{n}, but there is at least one of the vectors e_{n+1}, …, e_{k} which is a linear combination of three of the vectors e_{1}, …, e_{n}. Let, e.g.,

e_{n+1} = λ_{1}e_{1} + λ_{2}e_{2} + λ_{3}e_{3} ,

where λ_{1}, λ_{2}, λ_{3} are nonzero. Denote by L_{1} ⊂ ℝ^{n} the subspace spanned by e_{1}, e_{2}, e_{3}, and let L_{2} ⊂ ℝ^{n} be the subspace spanned by e_{4}, …, e_{n}. Since Z is indecomposable, there is a vector among e_{n+1}, …, e_{k} which is not contained in L_{1} ∪ L_{2}. Let, for definiteness,

e_{n+2} = μ_{2}e_{2} + μ_{3}e_{3} + μ_{4}e_{4} + μ_{5}e_{5} ,

where μ_{2} ≠ 0, μ_{4} ≠ 0 (and at least one of the numbers μ_{3}, μ_{5} is zero). Denote by q the composition of the projections parallel to e_{3}, e_{5}, e_{6}, …, e_{n}. Then q(Z) is a 3-dimensional zonotope, and c(Z) ≤ c(q(Z)) · 2^{n−3} (by Theorem 42.7 from [8]). Furthermore, q(Z) is the vector sum of the line segments

q(I_{1}), q(I_{2}), q(I_{4}), q(I_{n+1}), q(I_{n+2}), …, q(I_{k}) ,

i.e., the vector sum of at least five pairwise nonparallel segments. Moreover, q(Z) is indecomposable since

q(e_{n+1}) = λ_{1}q(e_{1}) + λ_{2}q(e_{2}), q(e_{n+2}) = μ_{2}q(e_{2}) + μ_{4}q(e_{4}) .

Now, by Lemma 1, c(q(Z)) ≤ 5, and hence c(Z) ≤ 5 · 2^{n−3}. Case 3) Each of the vectors e_{n+1}, …, e_{k} is a linar combination of exactly two of the vectors e_{1}, …, e_{n} with nonzero coefficients. Let, e.g.,

e_{n+1} = λ_{1}e_{1} + λ_{2}e_{2} .

Denoting by L_{1} the subspace spanned by e_{1}, e_{2}, and by L_{2} the subspace spanned by e_{3}, …, e_{n}, we conclude (as above) that there is a vector among e_{n+2}, …, e_{k} which is not contained in L_{1} ∪ L_{2}. Let, for definiteness,

e_{n+2} = μ_{1}e_{1} + μ_{3}e_{3}

(with μ_{1}, μ_{3} nonzero). Denote by q the composition of the projections parallel to e_{4}, …, e_{n}. Then q(Z) is a 3-dimensional zonotope as in Lemma 1, i.e., c(q(Z)) ≤ 5 and c(Z) ≤ 5 · 2^{n−3}.

□

Proof of Lemma 4. Let Z = Z_{1} ⊕ ⋯ ⊕ Z_{k}, where Z_{1}, …, Z_{k} are indecomposable. Denote dim Z_{i} by m_{i} and assume that that m_{1} ≥ m_{2} ≥ ⋯ ≥ m_{k}. If m_{2} ≠ 1 (i.e., the summands Z_{1}, Z_{2} are not one-dimensional and, by indecomposability, are not parallelotopes), then c(Z_{1}) ≤ 3 · 2^{m_{1}−2}, c(Z_{2}) ≤ 3 · 2^{m_{2}−2}, and hence

c(Z) ≤ 3 · 2^{m_{1}−2} · 3 · 2^{m_{2}−2} · 2^{m_{3}} ⋯ 2^{m_{k}} = \frac{9}{2} · 2^{n−3} < 5 · 2^{n−3} ,

i.e., the conclusion of the lemma holds. Let now m_{2} = 1, i.e., Z = Z_{1} ⊕ P where P is an (n−m_{1})-dimensional parallelotope. For m_{1} = 2, we obtain case (ii) of the Theorem. Even for m_{1} > 2 the lemma follows immediately from Lemmas 1, 3, and 6 (Lemma 6 is independently proved below). □

Proof of Lemma 5. Let Z = I_{1} + ⋯ + I_{k}, where I_{j} is a segment parallel to a belt vector w_{j} of the body B, j = 1, …, k. Denote the number c(Z) by m and choose some nonzero vectors e_{1}, …, e_{m} whose directions illuminate the whole boundary of the zonotope Z.

Let now a be an arbitrary boundary point of B, and K_{a} be the supporting cone of the body B at the point a, i.e., K_{a} is the intersection of all supporting half-spaces of B at the point a. Denote by l_{j} the line through a parallel to the vector w_{j}, j = 1, …, k. For every index j ∈ {i, …, k} we consider the following two possible cases:

a) The line l_{j} has a nonempty intersection with the interior of the cone K_{a}. Replacing, if necessary, w_{j} by −w_{j}, we may suppose that a + w_{j} ∈ int K_{a}. This means that there is a segment I′_{j} emanating from a which is equal and parallel to the segment I_{j} and satisfies the inclusion I′_{j} ⊂ K_{a}.

b) The line l_{j} has empty intersection with the interior of the cone K_{a}, i.e., l_{j} is a supporting line of the cone K_{a}, and hence l_{j} is a supporting line of the body B (passing through a). Since l_{j} ∥ w_{j} and w_{j} is a belt vector of B, at least one of the rays defined on the line l_{j} by the point a is a tangential ray of B at the point a. Replacing, if necessary, w_{j} by −w_{j} we may suppose that the ray r_{j}, emanating from a in the direction of the vector w_{j}, is a tangential ray of B at the point a. This means that the ray r_{j} is contained in the cone K_{a}. Denote by I′_{j} ∥ I_{j} the segment which is equal to I_{j} and is going from a in the direction of the vector w_{j}. Then I′_{j} ⊂ K_{a}.

Combining both the cases, we conclude that for every j ∈ {1, …, k} there is a segment I′_{j} with the endpoint a which is equal and parallel to I_{j} and I′_{j} ⊂ K_{a}.

Denote by Z′_{a} the set of all points (x_{1} −a)+⋯+(x_{k} −a) with x_{j} ∈ I′_{j}, j = 1, …, k. Then Z′_{a} is a zonotope which is obtained from Z by translation. Moreover, Z′_{a} ⊂ K_{a} and a is a vertex of Z′_{a}. Since the directions of the vectors e_{1}, …, e_{m} illuminate the whole boundary of the zonotope Z (and hence illuminate the boundary of Z′_{a}), there is an index i ∈ {1, …, m} such that the direction of the vector e_{i} illuminates the vertex a of the zonotope Z′_{a}. This means that for λ > 0 small enough we have a + λe_{i} ∈ ∫ Z′_{a}, and hence a + λe_{i} ∈ int K_{a} (since Z′_{a} ⊂ K_{a}). This implies that for λ > 0 small enough the inclusion a + λe_{i} ∈ int B holds, i.e., the direction of the vector e_{i} illuminates the boundary point a of the body B.

Thus every boundary point a of the body B is illuminated by at least one of the directions defined by the vectors e_{1}, …, e_{m}. This means that c(B) ≤ m, i.e., c(B) ≤ c(Z). □

Proof of Lemma 6. Let Γ be a supporting hyperplane of B at a regular boundary point a of B. By the definition of belt bodies, for each ε > 0 there are belt vectors h_{1}, …, h_{n−1} of B such that the hyperplane spanned by them is ε-close to Γ. But since there are only n + 1 belt vectors e_{1}, …, e_{n}, e_{n+1} of B, it follows that Γ is spanned by n−1 of these vectors. Thus every regular supporting hyperplane of B is spanned by some n − 1 vectors from {e_{1}, …, e_{n}, e_{n+1}}. Consequently there are only n(n+1) regular supporting hyperplanes of B. These hyperplanes we will call marked.

Let now Z be the polytope circumscribed about B with the n(n+1) marked hyperplanes as its facet hyperplanes, i.e., the affine hull of its facets. Assuming that B does not coincide with Z, we have a boundary point a of B which is an interior point of Z. Let b be a regular boundary point of the body B being close to a such that b ∈ int Z, and let Γ be the supporting hyperplane of B through b. Then Γ is not parallel to any marked hyperplane. But this is impossible, and this contradiction shows that B = Z. Finally we have to remark that Z is a zonotope (since its edges are parallel to the vectors e_{1}, …, e_{n}, e_{n+1} and each of its two-dimensional faces is a parallelogram). □

Proof of Lemma 7. Denote by B(M) the set of all unit belt vectors of the body M. Since M is indecomposable, the set B(M) is not splitable, i.e., there is no nontrivial decomposition ℝ^{n} = L_{1} ⊕ L_{2} with B(M) ⊂ L_{1} ∪ L_{2} (Theorem 43.4 in [8]). Consequently there exists a finite subset {e_{1}, …, e_{k}} ⊂ B(M) that also is not splitable. Take some segments I_{1}, …, I_{k} parallel to e_{1}, …, e_{k}, respectively. Then the n-dimensional tangential zonotope Z = I_{1} + ⋯ + I_{k} is not decomposable (again by Theorem 43.4 in [8]). □

Proof of the Theorem. Let B be an n-dimensional belt body different from the special bodies described in the theorem, and let

B = B_{1} ⊕ ⋯ ⊕ B_{k}

be its direct sum decomposition such that each B_{i} is indecomposable. Denote by m_{i} the dimension of B_{i}, and assume that m_{1} ≥ m_{2} ≥ ⋯ ≥ m_{k}. If m_{2} > 1, then c(B) ≤ \frac{9}{2} · 2^{n−3} < 5 · 2^{n−3} (cf. the proof of Lemma 4), i.e., the assertion of the Theorem holds.

Let now m_{2} = ⋯ = m_{k} = 1. Then m_{1} ≥ 3, since the cases (i) and (ii) in the theorem are excluded. If m_{1} = 3, then B_{1} is a belt body distinct from a parallelogramic dodecahedron. By Lemma 7, there is an m_{1}-dimensional, indecomposable, tangential zonotope Z_{1} of B_{1}. By Lemma 6, we may suppose that Z_{1} is distinct from a parallelogramic dodecahedron. Consequently (by Lemmas 1 and 5) c(B_{1}) ≤ c(Z_{1}) ≤ 5, and hence c(B) ≤ 5 · 2^{n−3}.

Let, finally, m_{1} ≥ 4. By Lemma 7, there is an indecomposable, m_{1}-dimensional, tangential zonotope Z_{1} of B_{1}. Consequently (by Lemmas 3 and 5) c(B_{1}) ≤ c(Z_{1}) ≤ 5 · 2^{m_{1}−3}, and hence c(B) ≤ 5 · 2^{n−3}. □

References

[1] Baladze, E.; Boltyanski, V.: Belt bodies and the Helly dimension (in Russian). Mat. Sbornik 186(2) (1995), 3–20.

[2] Bilinski, S.: Über die Rhombenisoeder. Glasnik Mat. Fiz. Astron. Društvo Mat. Fiz. Hrvatske, Ser. 2, 15 (1960), 251–263.

[3] Bolker, E. D.: Centrally symmetric polytopes. Proc. 12th Biannual Internat. Seminar of the Canadian Math. Congress (Vancouver 1969), Time Series and Stochastic Processes; Convexity and Combinatorics (R. Pyke, ed.), Canadian Math. Congress, Montreal 1970, pp. 255–263.

[4] Boltyanski, V.: The problem of illuminating the boundary of a convex body (in Russian). Izv. Mold. Fil. AN SSSR 76(10) (1960), 77–84.

[5] Boltyanski, V.: A solution of the illumination problem for belt bodies (in Russian). Mat. Zametki 58(4) (1996), 505–511.

[6] Boltyanski, V.; Gohberg, I.: Stories about covering and illumination of convex bodies. Nieuw Arch. Wisk. 13 (1995), 1–26.

[7] Boltyanski, V.; Martini, H.: Combinatorial geometry of belt bodies. Results Math. 28(1) (1995), 1–26.

[8] Boltyanski, V.; Martini, H.; Soltan, P.: Excursions into Combinatorial Geometry. Springer, Berlin et al., 1997.

[9] Boltyanski, V.; Soltan, P.: A solution of Hadwiger’s problem for zonoids. Combinatorica 12 (1992), 381–388.

[10] Cromwell, P. M.: Polyhedra. Cambridge University Press, Cambridge 1997.

[11] Gohberg, I. Z.; Markus, A. S.: One problem on covering convex figures by similar figures (in Russian). Izv. Mold. Fil. AN SSSR 76 (1960)(1), 87–90.

[12] Grünbaum, B.: Convex Polytopes. Wiley & Sons, London - New York - Sydney 1967.

[13] Hadwiger, H.: Ungelöste Probleme, Nr. 20. Elem. Math. 12 (1957), 121.

[14] Hadwiger, H.: Ungelöste Probleme, Nr. 38. Elem. Math. 15 (1960), 130–131.

[15] Lassak, M.: Solution of Hadwiger’s covering problem for centrally symmetric convex bodies in 𝔼^{3}. J. London Math. Soc. (2) 30 (1984), 355–361.

[16] Levi, F. W.: Überdeckung eines Eibereiches durch Parallelverschiebungen seines offenen Kerns. Arch. Math. 6 (1955), 369–370.

[17] Martini, H.: Some results and problems around zonotopes. Coll. Math. Soc. J. Bolyai 48 (Intuitive Geometry, Siofok 1985), North-Holland, Amsterdam et al. 1987, 383–418.

[18] Martini, H.; Soltan, V.: Combinatorial problems on the illumination of convex bodies. Aequationes Math. 57 (1999), 121–152.

[19] Ziegler, G. M.: Lectures on Polytopes. Springer, New York et al. 1995.

Received October 15, 1999