Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 43 (2002), No. 1, 153-169.

On the Characterization of some Families of Closed Convex Sets^{∗}

Miguel A. Goberna Valentin Jornet Margarita Rodriguez

Department of Statistics and Operations Research, Faculty of Sciences, University of Alicante, E-03080 Alicante, Spain e-mail: mgoberna@ua.es

Abstract. This paper deals with the characterization of the sums of compact convex sets with linear subspaces, simplices, sandwiches (convex hulls of pairs of parallel affine manifolds) and parallelotopes in terms of the so-called internal and conical representations, topological and geometrical properties. In particular, it is shown that a closed convex set is a sandwich if and only if its relative boundary is unconnected. The characterizations of families of closed convex sets can be useful in different fields of applied mathematics. For instance, it is proved that a bounded linear semi-infinite programming problem whose feasible set is the sum of a compact convex set with a linear subspace is necessarily solvable and has zero duality gap. MSC 2000: 52A20, 52A40, 52A41. Keywords: closed convex sets, simplices, sandwiches, parallelotopes, linear inequalities, connectivity.

1. Introduction

154 M. A. Goberna et.al.: On the Characterization of some Families of Closed Convex Sets

The characterization of families of closed convex sets can be useful from different perspectives. A linear semi-infinite programming (LSIP) problem consists of the minimization of a linear functional on a closed convex set in ℝ^{n} which is described by means of infinitely many linear inequalities. If the feasible set is the sum of a compact convex set with a linear subspace, we shall see that the boundedness of the LSIP problem entails its solvability. On the other hand, under suitable assumptions on the constraints system, it is possible to obtain an extreme point of the feasible set from any feasible solution without loss in the objetive (LSIP purification algorithms can be found in [2] and [5]) and then, starting at this initial extreme point, it is possible to construct a polygonal of linked edges along which the optimal functional decreases (an LSIP simplex method has been proposed in [1]). Obviously, the viability of an algorithm progressing on the boundary of the feasible region requires its connectivity by arcs. This paper characterizes the class of closed convex sets whose (relative) boundary is non-empty and connected by arcs.

∗This work was supported by the DGES of Spain, Grant PB98-0975.

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

On the other hand, typical geometric combinatorial problems are the characterization of those convex bodies (full dimensional closed convex sets) for which the minimum number of points (or directions) illuminating them in a certain sense has a given expression (see the survey in [9]).

This paper deals with the different ways of characterizing families of closed convex sets, focussing the attention on the sums of compact convex sets with linear subspaces and on three particular subfamilies of this class: simplices, sandwiches and parallelotopes.

Now, let us introduce some notation. The zero vector in ℝ^{n} will be represented by 0_{n} and the Euclidean open ball by B_{n}. Given a set X, ∅ ≠ X ⊂ ℝ^{n}, we denote by conv X, cone X, span X, aff X and X^{⊥} the convex hull of X, the conical convex hull of X, the linear subspace of ℝ^{n} spanned by X, the affine hull of X and {y ∈ ℝ^{n} | x′y = 0 for all x ∈ X}, respectively. Moreover, we define cone ∅ = {0_{n}}.

Given a convex set X, dim X represents its dimension (i.e., the dimension of aff X), O^{+}X the recession cone of X and, given x ∈ X, D (X; x) denotes the (convex) cone of feasible directions at x.

From the topological side, given X ⊂ ℝ^{n}, cl X, int X, bd X, rint X and rbd X denote the closure of X, the interior of X, the boundary of X, the relative interior of X and the relative boundary of X, respectively. We shall use the following result.

Lemma 1.1. (2.1 and 2.5 in [4]) Let ∅ ≠ X ⊂ ℝ^{n}. z ∈ rint cone X if, and only if, there exist points x^{i} ∈ X, i = 1, …, p, and corresponding positive scalars λ_{i}, i = 1, …, p, such

that span {x^{1}, …, x^{p}} = span X and z =∑^{p} ; i=1 λ_{i}x^{i}.

Any non-empty closed convex set C ⊂ ℝ^{n} admits different representations. First, C can be decomposed as the sum of its lineality space, L (C), with C ∩L (C)^{⊥} (this is the pointed cone of C if C is a convex cone). The last set turns out to be the sum of the convex hull of its set of extreme points, E (C) ≠ ∅, with the convex conical hull of its set of extreme directions, D (C) ([10], Th. 18.5), so that C = L (C) + E (C) + D (C). The triple (L (C) , E (C) , D (C)) constitutes the internal representation of C.

On the other hand, C is the intersection of all the supporting half-spaces to C, so that C is the solution set of a certain linear system σ = {a′_{t}x ≥ b_{t}, t ∈ T }, where a_{t} ∈ ℝ^{n} and b_{t} ∈ ℝ for all t ∈ T, the index set T being possibly infinite. Such a system σ is called an external representation of C. The non-homogeneous Farkas Lemma [15] establishes that a′x ≥ b is a consequence of the consistent system σ if, and only if,

\binom{a}{b} ∈ cl cone \{\binom{a_{t}}{b_{t}}, t ∈ T; \binom{0_{n}}{−1}\} .

From here, it can be easily shown that the right hand side cone,

K (C) := cl cone \{\binom{a_{t}}{b_{t}}, t ∈ T; \binom{0_{n}}{−1}\} ,

is the same for all the external representations of C ≠ ∅, so that, the so-called reference cone, K (C), can be seen as a conical representation of C. From K (C) it is possible to obtain

different external representations of C (e.g., \{a′x ≥ b, \binom{a}{b} ∈ I\}, where the index set I

is an arbitrary dense subset of K (C)). There exists a one-to-one correspondence between

non-empty closed convex sets in ℝ^{n} and closed convex cones in ℝ^{n+1} containing \binom{0_{n}}{−1}

but not containing \binom{0_{n}}{1} (their corresponding reference cones). The interest of the conical

representation derives from the fact that K (C) captures all the relevant information on C. For example, dim C = n−dim L [K (C)] (Theorem 5.8 in [5]) and the value of the optimization

problem P (c) : Min c′x s.t. x ∈ C, where c ∈ ℝ^{n}, is sup \{α ∈ ℝ | \binom{c}{α} ∈ K (C)\} (Theorem

8.1 (ii) in [5]), so that the properties of K (C) and P (c) are closely related to each other. Moreover, two closed convex sets, C_{1} and C_{2}, can be separated by a hyperplane if, and only if, K (C_{1}) ∩ [−K (C_{2})] contains at least one ray.

Uniqueness is a useful feature of both internal and conical representations, so that large families of non-empty closed convex sets can be characterized by means of the properties of their corresponding internal and conical representations (see the table below which comes from Ths. 5.8 and 5.13 in [5]).

C  Internal representation  Conical representation

affine manifold E (C) singleton, D (C) = {0_{n}}

The pointed cone of

K (C) is cone \{\binom{0_{n}}{−1}\}

polyhedral convex set E (C) polytope, D (C) polyhedral  K (C) polyhedral
convex body  dim L (C) + dim [E (C) + D (C)] = n  K (C) pointed

In Section 6 we shall make use of the following illumination concept which was introduced by Valentine [14]: given a convex body C and z ∉ C, x ∈ bd C is visible from z if ]x, z[ ∩ C = ∅. We denote by vis (C; z) the set of boundary points of C visible from z ∉ C. If C is compact, vis (C; z) ≠ bd C [12].

2. Characterizing the sums of compact convex sets with linear subspaces

Proposition 2.1. Given a closed convex set C ≠ ∅, the following conditions are equivalent to each other:

(i) C is the sum of a compact convex set with a linear subspace; (ii) E (C) is compact and D (C) = {0_{n}};

(iii) \binom{0_{n}}{−1} ∈ rint K (C); and (iv) L (C)^{⊥} = Π (K (C)), where Π denotes the vertical projection Π (x_{1}, …, x_{n+1}) =

(x_{1}, …, x_{n}).

Proof. (i) ⇒ (ii) If C = E + L, with E compact convex set and L linear subspace, then L (C) = L and C ∩ L^{⊥} = (E + L) ∩ L^{⊥} is the orthogonal projection of E onto L^{⊥}, so that it is the continuous image of a compact set. Hence E (C) = C ∩ L^{⊥} is compact.

(ii) ⇒ (iii) We assume that C = E (C) + L (C), with E (C) compact, E (C) ⊂ L (C)^{⊥}.

If L (C) = ℝ^{n}, C = ℝ^{n} and K (C) = cone \{\binom{0_{n}}{−1}\}, so that (iii) holds.

Let {u^{1}, …, u^{p}} be an orthonormal basis of L (C)^{⊥} ≠ {0_{n}} and let ρ > 0 such that ∥y∥ ≤ ρ for all y ∈ E (C).

Given x ∈ C, we can write x = y + z, y ∈ E (C) and z ∈ L (C), so that |±x′u^{j}| =

|±y′u^{j}| ≤ ρ and ±x′u^{j} ≥ −ρ. Hence \binom{±u^{j}}{−ρ} ∈ K (C), j = 1, …, p (Farkas Lemma).

Given \binom{a}{b} ∈ K (C), a′x ≥ b for all x ∈ C. If z ∈ L (C), taking an arbitrary point

\overline{x} ∈ E (C), we have \overline{x} + αz ∈ C for all α ∈ ℝ, so that a′ (\overline{x} + αz) ≥ b for all α ∈ ℝ, and this

entails a′z = 0. Hence a ∈ L (C)^{⊥} and we can write a = p ; ∑_{j=1} α_{j}u^{j} for certain scalars α_{j} ∈ ℝ,

j = 1, …, p.

Since

\binom{0_{n}}{−1} = (2pρ)^{−1} p ; ∑_{j=1} [\binom{u^{j}}{−ρ} + \binom{−u^{j}}{−ρ}] ,

we have

\binom{a}{b} = p ; ∑_{j=1} α_{j}\binom{u^{j}}{−ρ} − (b + ρ p ; ∑_{j=1} α_{j}) \binom{0_{n}}{−1} ∈ span \{\binom{±u^{j}}{−ρ}, j = 1, …, p\} ,

and the last set turns out to be span K (C). Hence we can apply Lemma 1.1 to conclude

that \binom{0_{n}}{−1} ∈ rint K (C).

(iii) ⇒ (iv) Since Π : ℝ^{n+1} → ℝ^{n} is linear and \binom{0_{n}}{−1} ∈ rint K (C) , we have 0_{n} ∈

rint Π [K (C)] (Th. 6.6 in [10]), with Π [K (C)] being a convex cone. Then Π [K (C)] is a linear subspace.

If Π [K (C)] = \{0_{n}\}, then K (C) = cone \{\binom{0_{n}}{−1}\} and C = ℝ^{n}, so that L (C) = ℝ^{n} and

L (C)^{⊥} = Π [K (C)]. We can assume without loss of generality that Π [K (C)] ≠ {0_{n}}. Let {v^{1}, …, v^{q}} an orthonormal basis of the linear subspace Π [K (C)]. Given k ∈

\{1, …, q\}, there exist scalars α_{k} and β_{k} such that \binom{v^{k}}{α_{k}} ∈ K (C) and \binom{−v^{k}}{−β_{k}} ∈ K (C),

so that α_{k} ≤ x′v^{k} ≤ β_{k} for all x ∈ C.

Now we shall prove that L (C) = [Π [K (C)]]^{⊥}.

In fact, if z ∈ L (C), taking an arbitrary \overline{x} ∈ C, we get, for k ∈ \{1, …, q\}, α_{k} ≤ (\overline{x} + αz)′ v^{k} ≤ β_{k} for all α ∈ ℝ, and this entails z′v^{k} = 0. Hence, L (C) ⊂ \{v^{1}, …, v^{q}\}^{⊥} = [Π [K (C)]]^{⊥}.

Conversely, if z ∈ [Π [K (C)]]^{⊥}, then a′z = 0 for all a ∈ ℝ^{n} such that \binom{a}{b} ∈ K (C)

for a certain b ∈ ℝ. Since \{a′x ≥ b | \binom{a}{b} ∈ K (C)\} is a linear representation of C, ±z is

a solution of the corresponding homogeneous system, so that ±z ∈ O^{+}C and z ∈ L (C). Hence, [Π [K (C)]]^{⊥} = L (C), so that (iv) holds.

(iv) ⇒ (i) If Π [K (C)] = {0_{n}}, C = ℝ^{n}. Assume dim Π [K (C)] = q, 1 ≤ q ≤ n. Let {v^{1}, …, v^{q}} be an orthonormal basis of Π [K (C)] and let α_{1}, …, α_{q}; β_{1}, …, β_{q} be scalars such that α_{k} ≤ x′v^{k} ≤ β_{k}, for all x ∈ C, k = 1, …, q. If q = n, C is compact. Otherwise L (C)^{⊥} = Π [K (C)] ≠ ℝ^{n} and we can select vectors v^{k} ∈ L (C), k = q + 1, …, n, such that {v^{1}, …, v^{n}} is an orthonormal basis of ℝ^{n}. Given x ∈ C ∩ L (C)^{⊥}, we have α_{k} ≤ x′v^{k} ≤ β_{k}, k = 1, …, q (since x ∈ C) and x′v^{k} = 0, k = q + 1, …, n (since x ∈ L (C)^{⊥}). Hence C ∩ L (C)^{⊥} is compact and C = [C ∩ L (C)^{⊥}] + L (C) is the aimed decomposition. □

Proposition 2.1 provides the next algebraic characterization of the sums of compact convex sets with linear subspaces from which we shall obtain nice properties of this class of feasible sets in LSIP.

Corollary 2.1. Let C = {x ∈ ℝ^{n} | a′_{t}x ≥ b_{t}, t ∈ T } ≠ ∅ and let M = cone {a_{t}, t ∈ T }. Then C is the sum of a compact convex set with a linear subspace if and only if M is a linear subspace.

Proof. Assume that C is the sum of a compact convex set with a linear subspace. According to Proposition 2.1 we can write C = E (C)+L (C), with E (C) compact and Π [K (C)] = L (C)^{⊥}.

Given t ∈ T, we have a_{t} = Π (a′_{t}, b_{t}) ∈ Π [K (C)], so that M ⊂ Π [K (C)]. On the other hand, if z ∈ Π [K (C)], there exists a sequence

\{z^{r}\} ⊂ cone \{\binom{a_{t}}{b_{t}}, t ∈ T; \binom{0_{n}}{−1}\}

such that z_{i} = lim_{r→∞} z_{i}^{r}, i = 1, …, n. For each z^{r} there exist a function λ^{r} : T ⟶ ℝ_{+} such that λ_{t}^{r} = 0 for all t ∈ T except for a finite number of indices and a non-negative real number μ^{r} such that

z^{r} =∑_{t∈T} λ_{t}^{r}\binom{a_{t}}{b_{t}} + μ^{r}\binom{0_{n}}{−1}.

Since ∑_{t∈T} λ_{t}^{r}a_{t} ∈ M, r = 1, 2, …, we have

z = lim_{r→∞} (z_{1}^{r}, …, z_{n}^{r})′ = lim_{r→∞}∑_{t∈T} λ_{t}^{r}a_{t} ∈ cl M.

We have shown that M ⊂ L (C)^{⊥} ⊂ cl M, so that cl M = L (C)^{⊥}. Hence,
L (C)^{⊥} = rint L (C)^{⊥} = rint cl M = rint M ⊂ M ⊂ L (C)^{⊥} ,

which proves that M = L (C)^{⊥} is a linear subspace.

Conversely, if M = ℝ^{n}, then C is compact (by Th. 9.3 in [5]). So, we assume that M is a linear subspace and cone {a_{t}, t ∈ T; ±v^{k}, k = 1, …, q} = ℝ^{n}, where {v^{1}, …, v^{q}} is a basis of M^{⊥}. Since L (C) = {y ∈ ℝ^{n} | a′_{t}y = 0, t ∈ T } = {a_{t}, t ∈ T }^{⊥}, L (C)^{⊥} = {a_{t}, t ∈ T }^{⊥⊥} = span {a_{t}, t ∈ T } = M (recall that M is a linear subspace). Then the assumption entails that

C ∩ L (C)^{⊥} = {x ∈ ℝ^{n} | a′_{t}x ≥ b_{t}, t ∈ T; x′v^{k} = 0, k = 1, …, q}

is compact, so that C = [C ∩ L (C)^{⊥}] + L (C) is the sum of a compact convex set with a linear subspace. □

Now assume that the LSIP problem P (c) has a finite value, v (c) , and its feasible set C is the sum of a compact convex set with a linear subspace. If c ∉ L (C)^{⊥}, then there exists a vector y ∈ L (C) such that either c′y < 0 or c′y > 0, so that either y or −y is a recession direction of C forming an acute angle with c, with v (c) = −∞ (contradiction). Hence c ∈ L (C)^{⊥} = M = rint M and this entails the solvability of P (c), its discretizability (an optimal solution can be obtained as the limit of optimal solutions of a sequence of finite subproblems) and the zero duality gap for any external representation of C (by Theorems 8.1, part (v), and 8.2 in [5]).

Corollary 2.2. Given a closed convex set C ≠ ∅, the following statements are equivalent to each other:

(i) C is a compact set; (ii) E (C) is compact and L (C) = D (C) = {0_{n}};

(iii) \binom{0_{n}}{−1} ∈ int K (C);

(iv) Π (K (C)) = ℝ^{n}; and

(v) P (c) is solvable for all c ∈ ℝ^{n}.

Proof. The equivalence between statements from (i) to (iv) is straightforward consequence of Proposition 2.1 and the arguments therein. Since (i) ⇒ (v) is trivial, we have just to prove that (v) ⇒ (i). In fact, if (i) fails there exists y ∈ O^{+}C, y ≠ 0_{n}, then P (−y) is not even bounded. Then (v) fails too. □

Hence the compact convex bodies are those closed convex sets for which the reference cone

is pointed and a neighbourdhood of \binom{0_{n}}{−1}. Significant geometric properties of this family

can be proved by means of LSIP theory ([6], [7] and [8]).

3. Characterization of simplices

C is a k-simplex if it is the convex hull of k + 1 points affinely independent. Obviously, any k-simplex is compact.

Proposition 3.1. Given a closed convex set C ≠ ∅, the following statements are equivalent to each other:

(i) C is a k-simplex; (ii) E (C) has k + 1 extreme points, dim E (C) = k and L (C) = D (C) = {0_{n}}; and

(iii) \binom{0_{n}}{−1} ∈ int K (C), dim L [K (C)] = n − k and the pointed cone of K (C) has k + 1

extreme rays.

Proof. (i) ⇔ (ii) is trivial.

(i) ⇒ (iii) Since every k-simplex is compact, we have \binom{0_{n}}{−1} ∈ int K (C). On the other

hand, according to the dimensional formula,

dim L [K (C)] = n − dim C = n − k.  (3.1)

Now, since C is a full-dimensional simplex in the affine manifold V := aff C, with dim V = k, there exist non-zero vectors {a_{i}, i = 1, …, k + 1} ⊂ V − V and corresponding scalars {b_{i}, i = 1, …, k + 1}, such that {x ∈ ℝ^{n} | a′_{i}x = b_{i}} is a supporting hyperplane at the relative interior points of the i-th facet, i = 1, …, k + 1. We can assume without loss of generality a′_{i}x ≥ b_{i} for all x ∈ C, i = 1, …, k + 1, so that C = {x ∈ V | a′_{i}x ≥ b_{i}, i = 1, …, k + 1}. Moreover, since dim V = k, we can write V = {x ∈ ℝ^{n} | a′_{i}x = b_{i}, i = k + 2, …, n + 1}, with

\{\binom{a_{i}}{b_{i}}, i = k + 2, …, n + 1\} linearly independent (if C is an n-simplex, then V = ℝ^{n} and

this part of the proof can be simplified).

Then,

K (C) = cone \{\binom{a_{i}}{b_{i}}, i = 1, …, k + 1; \binom{0_{n}}{−1}\} + span \{\binom{a_{i}}{b_{i}}, i = k + 2, …, n + 1\} ,

and we shall show that \binom{0_{n}}{−1} can be eliminated in this expression. To do this, we shall

appeal to a well-known characterization of the interior points of a convex cone (Lemma 1.1).

Since \binom{0_{n}}{−1} ∈ int K (C), we can write

\binom{0_{n}}{−1} =∑_{i∈I} λ_{i}\binom{a_{i}}{b_{i}} + μ\binom{0_{n}}{−1}, λ_{i} > 0 if i ≤ k + 1, μ ≥ 0,  (3.2)

for a certain set I ⊂ {1, …, n + 1}, with

span \{\binom{a_{i}}{b_{i}}, i ∈ I\} = ℝ^{n+1} if μ = 0

and

span \{\binom{a_{i}}{b_{i}}, i ∈ I; \binom{0_{n}}{−1}\} = ℝ^{n+1} if μ > 0.

If 0 ≤ μ < 1, from (3.2) we get

\binom{0_{n}}{−1} ∈ cone \{\binom{a_{i}}{b_{i}}, i = 1, …, k + 1\} + span \{\binom{a_{i}}{b_{i}}, i = k + 2, …, n + 1\} . (3.3)

We shall prove that this always happens when μ ≥ 0 by means of the following discussion.

If μ > 1, then (μ − 1) \binom{0_{n}}{1} =∑_{i∈I} λ_{i}\binom{a_{i}}{b_{i}} ∈ K (C), and this implies C = ∅. Alternatively,

if μ = 1, then we get ∑_{i∈I} λ_{i}\binom{a_{i}}{b_{i}} = 0_{n+1} and there will exist a j ≤ k + 1 such that λ_{j} > 0

(otherwise I ⊂ \{k + 2, …, n + 1\} and \{\binom{a_{i}}{b_{i}}, i = k + 2, …, n + 1\} is linearly dependent).

Then,

−\binom{a_{j}}{b_{j}} = ∑_{i∈I\\{j\}} λ_{j}^{−1}λ_{i}\binom{a_{i}}{b_{i}} ∈ K (C) ,

so that a′_{j}x = b_{j} for all x ∈ C. Hence a_{j} ∈ (V − V) ∩ (V − V)^{⊥} = {0_{n}}, i.e., a_{j} = 0_{n}. This is a contradiction.

From (3.3) we get

K (C) = cone \{\binom{a_{i}}{b_{i}}, i = 1, …, k + 1\} + span \{\binom{a_{i}}{b_{i}}, i = k + 2, …, n + 1\} .

Comparing dim span \{\binom{a_{i}}{b_{i}}, i = k + 2, …, n + 1\} = n − k with (3.1) we conclude that the

pointed cone of K (C) is

K̂ (C) := cone \{\binom{a_{i}}{b_{i}}, i = 1, …, k + 1\} .

If cone \{\binom{a_{j}}{b_{j}}\}, j ∈ \{1, …, k + 1\}, is not an extreme ray of K̂ (C), then we can write

\binom{a_{j}}{b_{j}} =_{∑^{k+1} ; i=1 ; i≠j} γ_{i}\binom{a_{i}}{b_{i}}, γ_{i} ≥ 0, i = 1, …, k + 1, i ≠ j,

so that K̂ (C) = cone \{\binom{a_{i}}{b_{i}}, i = 1, …, k + 1, i ≠ j\} and dim K̂ (C)≤k. Then dim K (C)=

dim K̂ (C)+dim L [K (C)] ≤ n and so int K (C)=∅. Hence \{cone \{\binom{a_{i}}{b_{i}}\} , i = 1, …, k + 1\}

is the set of extreme rays of K̂ (C).

(iii) ⇒ (i) The assumptions \binom{0_{n}}{−1} ∈ int K (C) and dim L [K (C)] = n − k guarantee

that C is compact and dim C = k, respectively. Let \{cone \{\binom{a_{i}}{b_{i}}\} , i = 1, …, k + 1\}

be the set of extreme rays of K̂ (C). According to the representation theorem, K̂ (C) =

cone \{\binom{a_{i}}{b_{i}}, i = 1, …, k + 1\} .

Let \{\binom{a_{i}}{b_{i}}, i = k + 2, …, n + 1\} be a basis of L [K (C)]. Then C = \{x ∈ V | a′_{i}x ≥ b_{i} ,

i = 1, …, k + 1}, where V = {x ∈ ℝ^{n} | a′_{i}x = b_{i}, i = k + 2, …, n + 1}. So, the number of extreme points of C is p ≤ \binom{k+1}{k} = k + 1. Assume that p < k + 1 and let \{x^{1}, …, x^{p}\} be the set of extreme points of C. The representation theorem yields C = conv {x^{1}, …, x^{p}}, so that dim C ≤ p − 1 < k. Hence p = k + 1 and {x^{1}, …, x^{k+1}} is affinely independent (otherwise, dim C < k). This completes the proof. □

4. Characterization of sandwiches

Two affine manifolds in ℝ^{n} (also called flats) of the same dimension, U_{1} and U_{2}, are parallel if U_{1} − U_{1} = U_{2} − U_{2} and U_{1} ∩ U_{2} = ∅. We say that a set is a k-sandwich when it is the convex hull of the union of two parallel affine manifolds of dimension k − 1. The next result establishes some elementary properties of the k-sandwiches that will be used later.

Proposition 4.1. Let C = conv (U_{1} ∪ U_{2}), where U_{1} and U_{2} are parallel affine manifolds, with dim U_{i} = k − 1, i = 1, 2. Let V := U_{1} − U_{1} = U_{2} − U_{2}, U_{i} ∩ V^{⊥} = {x^{i}}, i = 1, 2, and w = x^{2} − x^{1}. Then the following statements hold:

(i) C = V + [x^{1}, x^{2}] (and so C is the sum of a compact convex set with a linear subspace); (ii) dim C = k; (iii) aff C = U_{i} + span {w}, i = 1, 2; (iv) U_{i} = {x ∈ aff C | w′ (x − x^{i}) = 0}, i = 1, 2; and

(v) rint C = V + ]x^{1}, x^{2}[ and rbd C = U_{1} ∪ U_{2}.

Proof. The assumptions on U_{1} and U_{2} guarantee that x^{1} and x^{2} are well defined and w = x^{2} − x^{1} ≠ 0_{n}. Obviously, U_{i} = x^{i} + V, i = 1, 2.

(i) It is trivial. (ii) Obviously, for i = 1, 2, we have

U_{i} + span {w} = x^{i} + V + span {w} = V + (x^{i} + span {w}) = V + aff ([x^{1}, x^{2}]) ,

the last set being an affine manifold containing U_{1} and U_{2}. Hence, if {i, j} = {1, 2},

conv [U_{i} ∪ {x^{j}}] ⊂ C ⊂ U_{i} + span {w}.  (4.1)

Since x^{j} ∉ U_{i} and w ∈ V^{⊥}, we get from (4.1)

k ≤ dim conv [U_{i} ∪ {x^{j}}] ≤ dim C ≤ dim [U_{i} + span {w}] =

= dim [V + span {w}] = k.

Hence (ii) holds. (iii) It follows from the second inclusion in (4.1) and the equation dim C = dim [U_{i}+span {w}] which has proved above. (iv) Given x ∈ U_{i} = x^{i} + V, w′x = w′x^{i} because w ∈ V^{⊥}. Conversely, if x ∈ aff C satisfies w′ (x − x^{i}) = 0, then we can write (recall (iii)) x = x^{i} + v + αw, v ∈ V and α ∈ ℝ, with w′ (v + αw) = α ∥w∥^{2} = 0. This entails α = 0, i.e., x = x^{i} + v ∈ U_{i}.

(v) It is a straightforward consequence of Cor. 6.6.2 in [10] applied to (i). □

Next we give three different characterizations of the sandwiches. Another topological characterization will be given in Section 6.

Proposition 4.2. Let C be a non-empty closed convex set and let K (C) be its reference cone. The following statements are equivalent to each other:

(i) C is a k-sandwich. (ii) D (C) = {0_{n}}, E (C) is a proper closed segment and dim L (C) = k − 1. (iii) There exists a linear subspace V ⊂ (aff C) − C with dim V = k − 1, a non-zero vector

w ∈ V^{⊥}\ [(aff C) − C]^{⊥} and two real numbers α_{1} and α_{2}, such that α_{1} < α_{2} and

C = {x ∈ aff C | α_{1} ≤ w′x ≤ α_{2}} .

(iv) K (C) = K + W, where K is a pointed closed convex cone and W is a linear subspace

such that dim K = 2, dim W = n − k, \binom{0_{n}}{−1} ∈ rint K and

K ∩ (W + span \{\binom{0_{n}}{−1}\}) = cone \{\binom{0_{n}}{−1}\} .  (4.2)

Proof. We shall prove that (ii) ⇔ (i) ⇒ (iii) ⇒ (iv) ⇒ (i). (ii) ⇒ (i) If E (C) + D (C) = [x^{1}, x^{2}], with x^{1} ≠ x^{2}, defining U_{i} = x^{i} + L (C), it is easy to prove that C = conv (U_{1} ∪ U_{2}), U_{1} and U_{2} being parallel manifolds, such that dim U_{i} = k − 1, i = 1, 2.

(i) ⇒ (ii) It is straightforward consequence of statement (i) in Proposition 4.1.

(i) ⇒ (iii) Let C = conv (U_{1} ∪ U_{2}), where U_{1} and U_{2} are parallel affine manifolds. Let V, x^{1}, x^{2} and w be defined as in Proposition 4.1, whose statements (ii) and (iii) show that dim V = dim C − 1 and V ⊂ V + span {w} = (aff C) − C, respectively. Recalling the definition of w, we have w ∈ V^{⊥}\ [(aff C) − C]^{⊥}.

Let α_{i} = w′x^{i}, i = 1, 2. Obviously, α_{2} − α_{1} = ∥w∥^{2} > 0.

Since U_{i} = {x ∈ aff C | w′x = α_{i}}, i = 1, 2, according to statement (iv) in Proposition 4.1, we obtain

C = conv (U_{1} ∪ U_{2}) = {x ∈ aff C | α_{1} ≤ w′x ≤ α_{2}} .

(iii) ⇒ (iv) Let d = dim C. We shall distinguish the cases d = n and d < n.

M. A. Goberna et.al.: On the Characterization of some Families of Closed Convex Sets 163

Assume d = n. Since C = {x ∈ ℝ^{n} | α_{1} ≤ w′x ≤ α_{2}}, α_{1} < α_{2}, we have

K (C) = cone \{\binom{w}{α_{1}}, \binom{−w}{−α_{2}}, \binom{0_{n}}{−1}\} .

Moreover,

\binom{0_{n}}{−1} = \frac{1}{α_{2} − α_{1}} [\binom{w}{α_{1}} + \binom{−w}{−α_{2}}] ,

so that K (C) = cone \{\binom{w}{α_{1}}, \binom{−w}{−α_{2}}\} and Lemma 1.1 yields \binom{0_{n}}{−1} ∈ rint K (C).

Even more, since α_{1} ≠ α_{2}, \binom{w}{α_{1}} and \binom{−w}{−α_{2}} are linearly independent and K (C) is a two-dimensional pointed cone.

We shall finish this part of the proof showing that K (C) = K (C) + {0_{n+1}} is the aimed decomposition. In fact, if z ∈ K (C) ∩ span \{\binom{0_{n}}{−1}\}, it is possible to write

z = ρ_{1}\binom{w}{α_{1}} + ρ_{2}\binom{−w}{−α_{2}} = γ\binom{0_{n}}{−1}, ρ_{1} ≥ 0, ρ_{2} ≥ 0, γ ∈ ℝ.

This entails ρ_{1} = ρ_{2} and γ = ρ_{1} (α_{2} − α_{1}) ≥ 0, so that z ∈ cone \{\binom{0_{n}}{−1}\}. This proves

that K (C) ∩ span \{\binom{0_{n}}{−1}\} ⊂ cone \{\binom{0_{n}}{−1}\}, whereas the reverse inclusion holds trivially. Hence (4.2) holds. Now assume d < n. Let aff C ={x ∈ ℝ^{n} | a′_{i}x=b_{i}, i=1, …, n − d}, with {a_{i}, i=1, …, n − d} a linearly independent subset of ℝ^{n} and b_{i} ∈ ℝ, i=1, …, n − d.

Since C = {x ∈ aff C | α_{1} ≤ w′x ≤ α_{2}}, we have now

K (C) = cone \{±\binom{a_{i}}{b_{i}}, i = 1, …, n − d; \binom{w}{α_{1}}, \binom{−w}{−α_{2}}, \binom{0_{n}}{−1}\} =

= span \{\binom{a_{i}}{b_{i}}, i = 1, …, n − d\} + cone \{\binom{w}{α_{1}}, \binom{−w}{−α_{2}}, \binom{0_{n}}{−1}\} .

Let W := span \{\binom{a_{i}}{b_{i}}, i = 1, …, n − d\} and K := cone \{\binom{w}{α_{1}}, \binom{−w}{−α_{2}}, \binom{0_{n}}{−1}\}. W is a

linear subspace of ℝ^{n+1}, with dim W = n − d, and K (the same cone as in the case d = n) is a pointed closed convex cone, with dim K = 2 and \binom{0_{n}}{−1} ∈ rint K. Moreover, it is obvious that

cone \{\binom{0_{n}}{−1}\} ⊂ K ∩ span \{\binom{0_{n}}{−1}\} ⊂ K ∩ (W + span \{\binom{0_{n}}{−1}\}) .  (4.3)

Now consider an arbitrary z ∈ K ∩ (W + span \{\binom{0_{n}}{−1}\}). We can write

z = ρ_{1}\binom{w}{α_{1}} + ρ_{2}\binom{−w}{−α_{2}} =∑^{n−d} ; i=1 β_{i}\binom{a_{i}}{b_{i}} + γ\binom{0_{n}}{−1},  (4.4)

164 M. A. Goberna et.al.: On the Characterization of some Families of Closed Convex Sets

with ρ_{1} ≥ 0, ρ_{2} ≥ 0, β_{i} ∈ ℝ, i = 1, …, n − d, and γ ∈ ℝ. From (4.4),

(ρ_{2} − ρ_{1}) w+ ∑^{n−d} ; i=1 β_{i}a_{i} = 0_{n},

with {w; a_{i}, i = 1, …, n − d} being a linearly independent set because w ≠ 0_{n} and

w ∉ [(aff C) − C]^{⊥} = span {a_{i}, i = 1, …, n − d} .

Hence ρ_{1} = ρ_{2} and β_{i} = 0, i = 1, …, n − d, so that (4.4) reads

z = ρ_{1}\binom{0_{n}}{α_{1} − α_{2}} = γ\binom{0_{n}}{−1}

and we get γ = ρ_{1} (α_{2} − α_{1}) ≥ 0. Thus z = γ\binom{0_{n}}{−1} ∈ cone \{\binom{0_{n}}{−1}\}.

We have proved that

K ∩ (W + span \{\binom{0_{n}}{−1}\}) ⊂ cone \{\binom{0_{n}}{−1}\} ,

which together with (4.3) shows that (4.2) holds. (iv) ⇒ (i) Any two-dimensional pointed closed convex cone is the conical convex hull of two extreme directions (i.e., a plane acute angle). Let K = cone \{\binom{a}{α}, \binom{b}{β}\}, where \{\binom{a}{α}, \binom{b}{β}\}

is a linearly independent set in ℝ^{n+1}. Since we are assuming that \binom{0_{n}}{−1} ∈ rint K, we can write (by Lemma 1.1),

\binom{0_{n}}{−1} = ρ_{1}\binom{a}{α} + ρ_{2}\binom{b}{β}, ρ_{1} > 0, ρ_{2} > 0,  (4.5)

so that a ≠ 0_{n} (otherwise a = b = 0_{n} and \{\binom{a}{α}, \binom{b}{β}\} is linearly dependent). Defining w = ρ_{1}a ≠ 0_{n} and γ = ρ_{1}α, we get from (4.5)

K = cone \{\binom{w}{γ}, \binom{−w}{−γ − 1}\} .

Let \{\binom{a_{i}}{α_{i}}, i = 1, …, n − d\} a basis of W, with d = dim C. Since we are assuming that K (C) = K + W, we have

K (C) = cone \{±\binom{a_{i}}{α_{i}}, i = 1, …, n − d; \binom{w}{γ}, \binom{−w}{−γ − 1}\} ,

so that

C = {x ∈ ℝ^{n} | a′_{i}x = α_{i}, i = 1, …, n − d; γ ≤ w′x ≤ γ + 1} .  (4.6)

Let γ_{1} = γ, γ_{2} = γ + 1 and U_{j} = {x ∈ ℝ^{n} | a′_{i}x = α_{i}, i = 1, …, n − d; w′x = γ_{j}}, j = 1, 2. We shall prove that U_{j} ≠ ∅, j = 1, 2.

If U_{j} = ∅,

\binom{0_{n}}{1} ∈ K (U_{j}) = span \{\binom{a_{i}}{α_{i}}, i = 1, …, n − d; \binom{w}{γ_{j}}\}

and we can write

\binom{0_{n}}{1} =∑^{n−d} ; i=1 β_{i}\binom{a_{i}}{α_{i}} + β_{0}\binom{w}{γ_{j}}, β_{i} ∈ ℝ, i = 0, …, n − d.  (4.7)

From (4.7), β_{0}\binom{w}{γ_{j}} ∈ W + span \{\binom{0_{n}}{−1}\} and we shall discuss the sign of β_{0}.

If β_{0} > 0, then \binom{w}{γ_{j}} ∈ W + span \{\binom{0_{n}}{−1}\}. If j = 1,

\binom{w}{γ_{1}} ∈ K ∩ [W + span \{\binom{0_{n}}{−1}\}] = cone \{\binom{0_{n}}{−1}\} ,

according to (4.2), contradicting w ≠ 0_{n}. Alternatively, if j = 2, then

−\binom{w}{γ_{2}} ∈ K ∩ [W + span \{\binom{0_{n}}{−1}\}] = cone \{\binom{0_{n}}{−1}\} ,

and we get again w = 0_{n}.

If β_{0} < 0 we obtain w = 0_{n} in the same way.

Finally, if β_{0} = 0, (4.7) entails that {a′_{i}x = α_{i}, i = 1, …, n − d} is inconsistent, in contradiction with (4.6) (because C ≠ ∅).

We conclude that U_{1} and U_{2} are parallel affine manifolds and it can be easily shown that C = conv (U_{1} ∪ U_{2}).

This completes the proof. □

5. A topological characterization of k-sandwiches

From statement (v) in Proposition 4.1, it is clear that the relative boundary of any k-sandwich is not even connected. In order to prove the converse statement we shall use the following lemma.

Lemma 5.1. Let C be a closed convex set and let u ∈ ℝ^{n}\O^{+}C. If x^{i} ∈ C and u ∉ D (C; x^{i}), i = 1, 2, then x^{1} and x^{2} can be connected through a certain arc contained in bd C.

Proof. The statement is trivially true when n = 1 because the assumption on x^{1} and x^{2} entails x^{1} = x^{2}, so we assume n ≥ 2.

Since u ∉ O^{+}C and C is closed, for every x ∈ C there exists a unique non-negative real number φ (x) such that

φ (x) = max {t ∈ ℝ | x + tu ∈ C} .

u ∉ D (C; x^{i}) implies φ (x^{i}) = 0, and this for i = 1, 2. On the other hand, if x ∈ C, x + φ (x) u ∈ C whereas x + γu ∉ C for all γ > φ (x), so that x + φ (x) u ∈ bd C for all x ∈ C. We shall prove the continuity of φ |_{[x^{1},x^{2}]} , so that {x + φ (x) u | x ∈ [x^{1}, x^{2}]} will be the aimed arc connecting x^{1} with x^{2} and contained in bd C.

In fact, given two points of C, z^{1} and z^{2}, and a scalar λ ∈ [0, 1], since z^{i} + φ (z^{i}) u ∈ C, i = 1, 2, we have

(1 − λ) z^{1} + λz^{2} + [(1 − λ) φ (z^{1}) + λφ (z^{2})] u =
= (1 − λ) [z^{1} + φ (z^{1}) u] + λ [z^{2} + φ (z^{2}) u] ∈ C.

Hence (1 − λ) φ (z^{1}) + λφ (z^{2}) ≤ φ [(1 − λ) z^{1} + λz^{2}] and this means that φ is concave on C. In particular φ |_{[x^{1},x^{2}]} will be concave and so φ |_{[x^{1},x^{2}]} will be continuous on ]x^{1}, x^{2}[.

It remains to prove the continuity of φ at the extreme points of [x^{1}, x^{2}]. We assume the contrary.

If φ |_{[x^{1},x^{2}]} is not continuous at x^{i}, i ∈ {1, 2}, since φ (x^{i}) = 0 and φ (x) ≥ 0 for all x ∈ [x^{1}, x^{2}], there exists ε > 0 and a sequence {z^{k}}_{k=1}^{∞} ⊂ ]x^{1}, x^{2}[ such that lim_{k→∞} z^{k} = x^{i} and

φ (z^{k}) ≥ ε for all k ∈ ℕ. Then, for every k ∈ ℕ, we have

z^{k} + εu ∈ [z^{k}, z^{k} + φ (z^{k}) u] ⊂ C,

so that x^{i} + εu = lim_{k→∞} (z^{k} + εu) ∈ C and u ∈ D (C; x^{i}), contradicting the assumption. This completes the proof. □

Proposition 5.2. Let C be a non-empty closed convex set in ℝ^{n} that it is not an affine manifold, with dim C = k. Then the following statements are equivalent to each other:

(i) rbd C is not connected; (ii) rbd C is not connected by arcs; and 8iii) C is a k-sandwich.

Proof. (i) ⇒ (ii) It is trivial. (ii) ⇒ (iii) First we assume that C is full-dimensional. Thus the hypothesis will be that bd C is not connected by arcs.

If n = 1, since dim C = 1 and C ≠ ℝ, C will be either a closed half-line (and this is impossible because any singleton set is connected by arcs) or a closed proper segment in ℝ. Hence C is a sandwich.

So, we can assume without loss of generality that n ≥ 2.

Let x^{i} ∈ bd C, i = 1, 2, points that cannot be connected by means of any curve entirely contained in bd C.

Let c_{i} ≠ 0_{n}, such that c′_{i} (x − x^{i}) ≥ 0 for all x ∈ C, i = 1, 2. We denote by H_{i} := {x ∈ ℝ^{n} | c′_{i} (x − x^{i}) = 0}, i = 1, 2, the corresponding supporting hyperplanes to C. We shall prove that H_{1} ∩ H_{2} = ∅ by assuming the contrary. So, let z ∈ H_{1} ∩ H_{2}.

For {i, j} = {1, 2}, since z ∈ H_{i} and x^{j} ∈ C, we have

c′_{i} (z − x^{j}) = c′_{i} (z − x^{i} + x^{i} − x^{j}) = c′_{i} (x^{i} − x^{j}) ≤ 0.

If c′_{i} (z − x^{j}) = 0 then x^{j} ∈ H_{i} (because z ∈ H_{i}), so that [x^{i}, x^{j}] ⊂ C ∩ H_{i} ⊂ bd C (because H_{i} is supporting hyperplane to C), and this contradicts the assumption on x^{1} and x^{2}. Hence,

c′_{i} (z − x^{j}) < 0 if {i, j} = {1, 2} .  (5.1)

Now consider the vector u = 2z − (x^{1} + x^{2}). From (5.1), we get

c′_{i}u = c′_{i} (z − x^{i}) + c′_{i} (z − x^{j}) < 0, if {i, j} = {1, 2} .  (5.2)

(5.2) is incompatible with u ∈ O^{+}C because c′_{i} (x − x^{i}) ≥ 0 for all x ∈ C, i = 1, 2. Even more, also from (5.2), if t > 0, c′_{i} [(x^{i} + tu) − x^{i}] = t (c′_{i}u) < 0, so that x^{i} + tu ∉ C. This means that u ∉ D (C; x^{i}), i = 1, 2. Then we can apply Lemma 4.1 in order to obtain the aimed contradiction. Hence we have proved that H_{1} ∩ H_{2} = ∅, so that span {c_{1}} = span {c_{2}}. Next we shall prove that C = conv (H_{1} ∪ H_{2}).

Since x^{1} ∉ H_{2} and x^{2} ∉ H_{1} (otherwise H_{1} = H_{2}), c′_{2} (x^{1} − x^{2}) > 0 and c′_{1} (x^{1} − x^{2}) < 0, so that c_{2} is a negative multiple of c_{1} and we can write H_{i} = {x ∈ ℝ^{n} | c′x = α_{i}}, i = 1, 2, where c ≠ 0_{n}, c′x^{i} = α_{i}, i = 1, 2, and α_{1} < α_{2}. Since H_{i} is a supporting hyperplane to C at x^{i}, i = 1, 2, we have

C ⊂ {x ∈ ℝ^{n} | α_{1} ≤ c′x ≤ α_{2}} = conv (H_{1} ∪ H_{2}) .  (5.3)

In order to prove the reverse inclusion, let us consider an arbitrary vector v ∈ V := H_{1}−H_{1} = H_{2} − H_{2}.

If v ∉ O^{+}C, there exist non-negative real numbers

λ_{i} := max {t ∈ ℝ | x^{i} + tv ∈ C} , i = 1, 2.

Then [x^{i}, x^{i} + λ_{i}v] ⊂ C ∩ H_{i} ⊂ bd C, i = 1, 2. On the other hand, there exists an arc connecting x^{1} + λ_{1}v with x^{2} + λ_{2}v which is completely contained in bd C (because v ∉ D (C; x^{i} + λ_{i}v), i = 1, 2, and so Lemma 5.1 applies again), and this means that x^{1} can be connected with x^{2} by means of an arc contained in bd C, composed by three linked arcs. This is a contradiction, so that V ⊂ O^{+}C.

Hence H_{i} = x^{i} + V ⊂ C + O^{+}C = C, i = 1, 2, and we obtain

conv (H_{1} ∪ H_{2}) ⊂ C.  (5.4)

From (5.3) and (5.4), we conclude that C = conv (H_{1} ∪ H_{2}) is a full-dimensional sandwich.

Now we assume that k < n. Then C is a full-dimensional closed convex set, in aff C, such that its boundary, in the topology of aff C, is not connected by arcs. Applying the previous argument, C turns out to be a full-dimensional sandwich in aff C, i.e., a k-sandwich. (iii) ⇒ (i) It is straightforward consequence of statement (v) in Proposition 4.1. □

6. Characterization of n-simplices, n-sandwiches and parallelotopes

In a recent paper of Martini and Soltan [9], it has been proved that, given a compact convex body C, C is an n-simplex if, and only if, for all z^{1} ∉ C there exists another point z^{2} ∉ C such that vis (C; z^{1}) ∪ vis (C; z^{2}) = bd C, i.e., the whole set C can be seen from {z^{1}, z^{2}}.

The compactness of C is essential in this characterization, even reinforcing the above condition with vis (C; z) ≠ bd C for all z ∉ C (a consequence of the boundedness of C). In fact, given an n-sandwich C = {x ∈ ℝ^{n} | α_{1} ≤ a′x ≤ α_{2}}, with a ≠ 0_{n} and α_{1} < α_{2}, and z ∉ C, we have

vis (C; z) = \{ \begin{matrix}\{x ∈ ℝ^{n} | a′x = α_{1}\} & if & a′z < α_{1} \\ \{x ∈ ℝ^{n} | a′x = α_{2}\} & if & a′z > α_{2} \end{matrix} ,  (6.1)

so that the n-sandwiches satisfy the above conditions. Unfortunately, they are not the only unbounded convex bodies satisfying these conditions. This is the case of every closed convex set C such that E (C) is an (n − 1)-simplex, L (C) is a line through the origin and D (C) = {0_{n}} (e.g., the cartesian product S ×ℝ where S is an (n − 1)-simplex in ℝ^{n−1}). Nevertheless, the n-sandwiches (the class of convex bodies with non-empty unconnected boundary) can also be characterized in terms of visibilities.

Proposition 6.1. Let C ≠ ℝ^{n} be a convex body. Then C is an n-sandwich if, and only if, vis (C; z) is a hyperplane and vis (C; z) ≠ bd C for all z ∉ C.

Proof. The direct statement is a straightforward consequence of (6.1). Assume that vis (C; z) is a hyperplane different of bd C for all z ∉ C. Since {vis (C; z) , z ∉ C} is a covering of bd C, bd C turns out to be the union of at least two hyperplanes. Assuming that bd C contains two non-parallel hyperplanes, we shall obtain a contradiction. In fact, let H_{i} = {x ∈ ℝ^{n} | a′_{i}x = b_{i}}, with a′_{i}x ≥ b_{i} for all x ∈ C, i = 1, 2, with span {a_{1}} ≠ span {a_{2}}. Since H_{1} is not contained in {x ∈ ℝ^{n} | a′_{2}x ≥ b_{2}}, there exists x^{1} ∈ ℝ^{n} such that a′_{1}x^{1} = b_{1} and a′_{2}x^{1} < b_{2}. Then x^{1} ∈ H_{1}\C, contradicting H_{1} ⊂ bd C ⊂ C.

Since bd C is the union of at least two parallel hyperplanes, bd C is unconnected, and so C is an n-sandwich by Proposition 5.2. □

A parallelotope can be defined as the intersection of a family of n “independent” n-sand-wiches, i.e., a set of the form C = ∩^{n}_{i=1} C_{i}, with C_{i} = {x ∈ ℝ^{n} | α_{i} ≤ a′_{i}x ≤ β_{i}}, α_{i} < β_{i} for i = 1, …, n, and {a_{i}, i = 1, …, n} linearly independent. Consequently,

K (C) = cone \{\binom{a_{i}}{α_{i}}, i = 1, …, n; −\binom{a_{i}}{β_{i}}, i = 1, …, n; \binom{0_{n}}{−1}\}

whereas E (C) is the sum of n segments, [x^{i}, y^{i}], i = 1, …, n, such that {y^{i} − x^{i}, i = 1, …, n} is linearly independent, and L (C) = D (C) = {0_{n}}. A parallelotope is a particular class of n-zonotope (convex body that can be expressed as the sum of finitely many compact segments). As the n-simplices and the n-sandwiches, the parallelotopes not only can be characterized by means of their conical and internal representations but also through their geometric combinatorial properties. In fact, a given n-zonotope C is a parallelotope if, and only if, the minimum number of smaller homothetic copies of C covering C (or directions, or points, illuminating C) is exactly 2^{n} ([11] and [13]).

Parallelotopes, n-simplices and n-sandwiches are only some of the families of convex bodies enjoying nice combinatorial, optimality and separability properties (see, e.g., [9], [5] and [3], respectively). The characterization of all these families in terms of their internal and conical representations and their illumination properties are challenging open problems.

Acknowledgments. The authors are indebted to Dr. S. Segura for his valuable comments and suggestions.

References

[1] Anderson, E. J.; Goberna, M. A.; Lopez, M. A.: Simplex-like trajectories on quasipolyhedral sets. Math. Oper. Res., to appear.

[2] Anderson, E. J.; Nash, P.: Linear Programming in Infinite Dimensional Spaces. J. Wiley, New York 1987. Zbl 0632.90038

[3] Bair, J.; Fourneau, R.: Etude Géometrique des Espaces Vectoriels II: Polyèdres et Polytopes Convexes. Springer-Verlag, Berlin 1980. Zbl 0481.52004

[4] Fischer, T.: Strong unicity and alternation for linear optimization. J. Opt. Theor. Appl. 69 (1991), 251–267. Zbl 0725.90093

[5] Goberna, M. A.; López, M. A.: Linear Semi-Infinite Optimization. J. Wiley, Chichester, England, 1998. Zbl 0909.90257

[6] Juhnke, F.: Inradius und Dicke konvexer Körper aus optimierungstheoretischer Sicht. Beiträge Algebra Geom. 27 (1988), 13–20. Zbl 0683.52005

[7] Juhnke, F.: Das Umkugelproblem und lineare semiinfinite Optimierung. Beiträge Algebra Geom. 28 (1988), 147–156. Zbl 0689.52003

[8] Juhnke, F.; Sarges, O.: Minimal spherical shells and linear semi-infinite optimization. Beiträge Algebra Geom. 41 (2000), 93–105. Zbl 0142.8664

[9] Martini, H.; Soltan, V.: Combinatorial problems on the illumination of convex bodies. Aeq. Mathematicae 57 (1999), 121–152. Zbl 0937.52006

[10] Rockafellar, R. T.: Convex Analysis. Princeton Univ. Press, Princeton, New Jersey 1970.

[11] Soltan, P.: On the covering of polyhedra by homothetic images. Soviet. Math. Dokl. 13 (1972), 155–159. Zbl 0245.52010

[12] Soltan, P.: External illumination according to L. Fejes Tóth. Studia Sci. Math. Hungar. 28 (1993), 473–483. Zbl 0817.52013

[13] Soltan, P.: An illumination problem. Studia Sci. Math. Hungar. 29 (1994), 25–32. Zbl 0815.52007

[14] Valentine, F. A.: Visible shorelines. Amer. Math. Monthly 77 (1970), 146–152. Zbl 0189.52903

[15] Zhu, Y. J.: Generalizations of some fundamental theorems on linear inequalities. Acta Math. Sinica 16 (1966), 25–40. Zbl 0147.34102

Received December 11, 2000