Local Conicity and Polyhedrality of Convex Sets

Abstract

A convex set in the n-dimensional vector space is called boundedly polyhedral provided its intersection with every polytope is a polytope (possibly empty). We refine existing results on bounded polyhedrality of line-free closed convex sets in terms of local conicity and local polyhedrality at their extreme points and halflines.

1 Introduction

Following Klee [14], we say that a convex set K in the n-dimensional Euclidean space ${\mathbb {R}}^n$ is boundedly polyhedral provided its intersection with every polytope is again a polytope (possibly empty). Other terms are quasi-polyhedral set [1, 2] and generalized polyhedron [3, 11]. Boundedly polyhedral sets are viewed as generalizations of polyhedra and often are interpreted as solution sets of locally finite systems of linear inequalities (see, e. g., [1, 2, 12, 13, 17]). Bounded polyhedrality plays an important role in the study of upper semi-continuity of convex functions [7,8,9], Lipschitzian properties of affine transformations [23], and sharp continuity of metric projections [10].

There are various characterizations of boundedly polyhedral sets in terms of local polyhedrality and local conicity. In Sect. 2 we provide a summary of existing and new results on local conicity of convex sets. Furthermore, we refine some known characteristic properties of boundedly polyhedral sets by reducing the sets of points to be tested for local polyhedrality or local conicity (see Sect. 3).

We conclude this section with necessary definitions, notation, and results on convex sets in the n-dimensional Euclidean space ${\mathbb {R}}^n$ (see, e. g., [18] for details). By an r-dimensional plane L in ${\mathbb {R}}^n$, where $0 \le r \le n$, we mean a translate of a suitable r-dimensional subspace S of ${\mathbb {R}}^n$: $L = c + S$, where $c \in {\mathbb {R}}^n$. Given distinct points $u, v \in {\mathbb {R}}^n$, we denote by [u, v] and (u, v) the closed segment and the open segment with endpoints u and v, and $[u, v \rangle$ stands for the closed halfline through v with endpoint u.

The closed and open balls with center $x \in {\mathbb {R}}^n$ and radius $\rho > 0$ are denoted by $B_\rho (x)$ and $U_\rho (x)$, respectively. As usual, ${\mathrm {cl\,}}X$ and ${\mathrm {int\,}}X$ stand for the closure and interior of a set $X \subset {\mathbb {R}}^n$. The convex hull and affine span of X are denoted by ${\mathrm {conv\,}}X$ and ${\mathrm {aff\,}}X$, respectively, and ${\mathrm {dim\,}}X$ is defined as the dimension of the plane ${\mathrm {aff\,}}X$. We say that a point $x \in X$ is isolated in X provided there is an open ball $U_\rho (x) \subset {\mathbb {R}}^n$ such that $X \cap U_\rho (x) = \varnothing$. Furthermore, a set $X \subset {\mathbb {R}}^n$ is called discrete if every point $x \in X$ is isolated in X.

In what follows, K denotes a proper convex set in ${\mathbb {R}}^n$ (that is, $\varnothing \ne K \ne {\mathbb {R}}^n$), and ${\mathrm {rint\,}}K$ and ${\mathrm {rbd\,}}K$ mean its relative interior and relative boundary (while ${\mathrm {rint\,}}K \ne \varnothing$, the set ${\mathrm {rbd\,}}K$ is nonempty if and only if K is not a plane).

An extreme face of K is a nonempty convex subset F of K such that, for any points $x, y \in K$ and a scalar $\lambda \in \, (0, 1)$, the inclusion $(1 - \lambda ) x + \lambda y \in F$ is possible only if $x, y \in F$. For a given point $u \in K$, there is the smallest extreme face of K, denoted $F_u$, which contains u. Furthermore, $F_u \subset {\mathrm {rbd\,}}K$ provided $u \in {\mathrm {rbd\,}}K$. The extreme face $F_u$ is the largest convex subset of K containing u in its relative interior. If $F_u \ne \{ u \}$, then $F_u$ is the union of all segments $[v, w] \subset K$ satisfying the condition $u \in (v, w)$.

Zero-dimensional extreme faces of K are called extreme points of K, and their union is denoted ${\mathrm {ext\,}}K$. The union of extreme halflines of K is denoted ${\mathrm {extr\,}}K$, while the union of all extreme faces of K of dimension at most one (which includes points, segments, halflines, and lines) is denoted ${\mathrm {ext}}_1 K$. A closed convex set $K \subset {\mathbb {R}}^n$ which does not contain lines (and thus is called line-free) is expressible as the convex hull of its extreme points and extreme halflines:

$$\begin{aligned} K = {\mathrm {conv\,}}({\mathrm {ext\,}}K \cup {\mathrm {extr\,}}K). \end{aligned}$$

(1)

The lineality space of a closed convex set $K \subset {\mathbb {R}}^n$, denoted ${\mathrm {lin\,}}K$, is the largest subspace $T \subset {\mathbb {R}}^n$ such that $K = K + T$. If the subspace S is the orthogonal complement of ${\mathrm {lin\,}}K$ in ${\mathbb {R}}^n$, then

$$\begin{aligned} K = (K \cap S) + {\mathrm {lin\,}}K, \end{aligned}$$

(2)

where $K \cap S$ is a line-free closed convex set. Consequently, any extreme face F of K can be expressed as $F = G + {\mathrm {lin\,}}K$, where G is an extreme face of $K \cap S$. In particular, any planar extreme face F of K has the form $F = x + {\mathrm {lin\,}}K$, where $x \in {\mathrm {ext\,}}(K \cap S)$.

By a convex cone with apex u we mean a convex set $C \subset {\mathbb {R}}^n$ such that $u + \lambda (x - u) \in C$ for all $\lambda \ge 0$ and $x \in C$ (obviously, this definition implies that $u \in C$, although a stronger condition $\lambda > 0$ can be beneficial; see, e. g., [15]). It is known that an apex u of C belongs to ${\mathrm {rbd\,}}C$ if and only if C is not a plane. Furthermore, ${\mathrm {cl\,}}C$ is a convex cone with apex u. The cone C is called pointed if it has a unique apex. We will need the following simple lemma.

Lemma 1

If a closed convex cone $C \subset {\mathbb {R}}^n$ with apex u is contained in another closed convex cone $D \subset {\mathbb {R}}^n$ with apex v, then $(v - u) + C \subset D$. Furthermore, $C \subset {\mathrm {rint\,}}D$ provided $u \in {\mathrm {rint\,}}D$. $\square$

Given a convex set $K \subset {\mathbb {R}}^n$ and a point $u \in {\mathbb {R}}^n$, the cone with apex u generated by K is defined by

$$\begin{aligned} C_u(K) = \{ u + \lambda (x - u) : \lambda \ge 0, \ x \in K \}. \end{aligned}$$

In other words, $C_u(K)$ is the smallest convex cone with apex u containing K. We observe that $C_u(K)$ may be nonclosed even if K is a closed set. For any point $u \in K$ and an open ball $U_\rho (u) \subset {\mathbb {R}}^n$, one has

$$\begin{aligned} C_u(K) = C_u(K \cap U_\rho (u)). \end{aligned}$$

(3)

Furthermore, ${\mathrm {aff\,}}C_u(K) = {\mathrm {aff\,}}K$ for all $u \in K$, and $C_u(K) = {\mathrm {aff\,}}K$ if and only if $u \in {\mathrm {rint\,}}K$. For a point $u \in K$, the cone $C_u(K)$ is pointed if and only if $u \in {\mathrm {ext\,}}K$.

A polyhedron is the intersection of finitely many closed halfspaces of ${\mathbb {R}}^n$. Bounded polyhedra are called polytopes. A line-free closed convex set in ${\mathbb {R}}^n$ is a polyhedron if and only if it has finitely many extreme points and extreme halflines. If $P \subset {\mathbb {R}}^n$ is a polyhedron and $u \in P$, then the generated cone $C_u(P)$ is polyhedral.

2 Local Conicity and Polyhedrality

Bounded polyhedrality of a convex set $K \subset {\mathbb {R}}^n$ is related to three local properties of K: polyhedrality, conicity, and closedness of generated cones $C_x(K)$. Following [14], we say that K is polyhedral at a point $x \in K$ if there is a polyhedral neighborhood of x in K. We recall that a polyhedron $Q \subset K$ is a polyhedral neighborhood of x in K provided there is an open ball $U_\rho (x) \subset {\mathbb {R}}^n$ such that $K \cap U_\rho (x) \subset Q$. Obviously, here $U_\rho (x)$ can be replaced with the respective closed ball $B_\rho (x)$. The following criterion of local polyhedrality is obtained in [14, Corollary 3.3].

Lemma 2

([14]). A convex set $K \subset {\mathbb {R}}^n$ is polyhedral at a point $x \in K$ if and only if the generated cone $C_x(K)$ is polyhedral. $\square$

A criterion of local non-polyhedrality is proved in [7]: A convex set $K \subset {\mathbb {R}}^n$ is not polyhedral at a point $x \in K$ if and only if there is a closed convex set $M \subset {\mathbb {R}}^n$ containing x such that $x \in {\mathrm {cl\,}}(K \setminus M)$, yet $[x, z] \not \subset K \setminus M$ whenever $z \in K \setminus M$.

In a standard way, a convex set $K \subset {\mathbb {R}}^n$ is called conic at a point $x \in K$ provided there is a convex cone $C \subset {\mathbb {R}}^n$ with apex x and an open ball $U_\rho (x) \subset {\mathbb {R}}^n$ such that

$$\begin{aligned} K \cap U_\rho (x) = C \cap U_\rho (x). \end{aligned}$$

(4)

An elementary geometric argument implies the following lemma (see, e. g., [1, 16, 22]).

Lemma 3

If a convex set $K \subset {\mathbb {R}}^n$ is polyhedral at a point $x \in K$, then K is conic at x. $\square$

It is possible to show (see, e. g., [18, Theorem 7.6]) that the cone C in (4) is uniquely determined and

$$\begin{aligned} {\mathrm {cl\,}}K \cap U_\rho (x) = {\mathrm {cl\,}}C \cap U_\rho (x). \end{aligned}$$

(5)

The same reference implies the lemma below.

Lemma 4

A convex set  $K \subset {\mathbb {R}}^n$ is conic at a point  $x \in K$ if and only if there is an open ball  $U_\rho (x) \subset {\mathbb {R}}^n$ such that

$$\begin{aligned} K \cap U_\rho (x) = C_x(K) \cap U_\rho (x), \end{aligned}$$

(6)

where $C_x(K)$ denotes the cone with apex x generated by K. $\square$

A combination of the equalities (5) and (6) implies the following corollary.

Corollary 1

If a closed convex set  $K \subset {\mathbb {R}}^n$ is conic at a point  $x \in K$, then the cone $C_x(K)$ is closed. $\square$

The example below illustrates the fact that the closedness of $C_x(K)$ does not imply the conicity of K at x. Similar examples can be found in [16, 18, 22], and some others.

Example 1

Let $\varGamma$ be the quarter arc of the unit circle in the yz-coordinate plane of ${\mathbb {R}}^3$, as depicted in Fig. 1.

Fig. 1

Non-conic point u with closed generated cone $C_u(K)$

Denote by c and e the endpoints of $\varGamma$. Choose a nonzero point u on the x-axis, and consider the cone $C = C_u({\mathrm {conv\,}}(\varGamma \cup \{ o \}))$. Obviously, C is closed and convex. Denote by $\varLambda$ a smooth curve with endpoints u and c which lies on the boundary of C such that the closed segment [u, e] is tangent to $\varLambda$ and meets $\varLambda$ at u only. The set $K = {\mathrm {conv\,}}([e, o] \cup \varLambda )$ is compact and convex. Also, $C = C_u(K)$. At the same time, K is not conic at u because

$$\begin{aligned} K \cap U_\rho (u) \ne C_u(K) \cap U_\rho (u) \ \ \text {for all} \ \ \rho > 0. \end{aligned}$$

We observe that a convex set $K \subset {\mathbb {R}}^n$ is conic at every point $x \in {\mathrm {rint\,}}K$. Indeed, by the definition of ${\mathrm {rint\,}}K$, there is an open ball $U_\rho (x) \subset {\mathbb {R}}^n$ such that ${\mathrm {aff\,}}K \cap U_\rho (x) \subset K$. Furthermore, $C_x(K) = {\mathrm {aff\,}}K$, which gives the desired equality (6). The following two lemmas characterize those points from ${\mathrm {rbd\,}}K$ and ${\mathrm {ext\,}}K$, respectively, at which K is conic.

Lemma 5

([19]). Let  $K \subset {\mathbb {R}}^n$ be a closed convex set, with ${\mathrm {dim\,}}K \ge 2$, and let $x \in {\mathrm {rbd\,}}K$. Then K is conic at x if and only if there is an open ball  $U_\rho (x) \subset {\mathbb {R}}^n$ such that $[x, z] \subset {\mathrm {rbd\,}}K$ whenever $z \in {\mathrm {rbd\,}}K \cap U_\rho (x)$. $\square$

Corollary 2

([19]). A line-free closed convex set $K \subset {\mathbb {R}}^n$ is conic at a point $x \in {\mathrm {ext\,}}K$ if and only if x is an isolated point in ${\mathrm {ext\,}}K$. $\square$

The assertion of Corollary 2 does not hold if the point x is not in ${\mathrm {ext\,}}K$. Indeed, let $K \subset {\mathbb {R}}^3$ be the bounded circular cylinder given by

$$\begin{aligned} K = \{ (x, y, z) : x^2 + y^2 \le 1, 0 \le z \le 1 \}. \end{aligned}$$

The boundary point $u = (1,0,0.5)$ of K is at distance 0.5 from ${\mathrm {ext\,}}K$, while K is not conic at u.

The next theorem generalizes Corollary 2 to the case of arbitrary points in ${\mathrm {rbd\,}}K$. Denote by E(x) the union of all extreme faces of a closed convex set K which do not contain a given point $x \in {\mathrm {rbd\,}}K$ (we observe that $E(x) = \varnothing$ if and only if K is a closed convex cone with apex x, see [18, Corollary 11.35]).

Theorem 1

A closed convex set $K \subset {\mathbb {R}}^n$ is conic at a point $x \in {\mathrm {rbd\,}}K$ if and only if $x \notin {\mathrm {cl\,}}E(x)$.

Proof

Assume first that K is conic at x. By Lemma 5, there is an open ball $U_\rho (x) \subset {\mathbb {R}}^n$ such that $[x, z] \subset {\mathrm {rbd\,}}K$ whenever $z \in {\mathrm {rbd\,}}K \cap U_\rho (x)$. Choose any extreme face G of K which does not contain x. Clearly, $G \subset {\mathrm {rbd\,}}K$ (otherwise, $x \in K = G$). We assert that $G \cap U_\rho (x) = \varnothing$. Indeed, assume for a moment the existence of a point $z \in G \cap U_\rho (x)$. Then $z \in {\mathrm {rbd\,}}K \cap U_\rho (x)$ due to $G \subset {\mathrm {rbd\,}}K$. By the choice of $U_\rho (x)$, there is a point $u \in {\mathrm {rbd\,}}K \cap U_\rho (x)$ such that $z \in (x, u) \subset {\mathrm {rbd\,}}K$. Denote by $F_z$ the smallest extreme face of K containing z. Then $z \in [v, w] \subset F_z \subset G$, contrary to the choice of G. Summing up, $G \cap U_\rho (x) = \varnothing$. The above argument implies that x is at a distance $\rho$ or more from any extreme face of K. Thus, $x \notin {\mathrm {cl\,}}E(x)$.

Conversely, assume that $x \notin {\mathrm {cl\,}}E(x)$. Equivalently, there is a scalar $\rho > 0$ such that $E(x) \cap U_\rho (x) = \varnothing$. We assert that $[x, z] \subset {\mathrm {rbd\,}}K$ whenever $z \in {\mathrm {rbd\,}}K \cap U_\rho (x)$. Indeed, assume for a moment the existence of a point $u \in {\mathrm {rbd\,}}K \cap U_\rho (x)$ such that $[x, u] \not \subset {\mathrm {rbd\,}}K$. Then $(x, u) \subset {\mathrm {rint\,}}K$. Denote by $F_u$ the smallest extreme face of K containing u. Clearly, $x \notin F_u$ (otherwise $[x, u] \subset F_u \subset {\mathrm {rbd\,}}K$). Hence $F_u \subset E(x)$, which gives

$$\begin{aligned} \varnothing \ne F_u \cap U_\rho (x) \subset E(x) \cap U_\rho (x), \end{aligned}$$

a contradiction with the choice of $U_\rho (x)$. $\square$

One more characteristic property of points of local conicity follows the method of proof of Theorem 1 from [6]. In a standard way, the cone $T_x(K) = {\mathrm {cl\,}}C_x(K)$ is called the tangent cone of K with apex $x \in K$.

Theorem 2

Given a closed convex set  $K \subset {\mathbb {R}}^n$ and a point  $x \in K$, the conditions below are equivalent:

• (a) K is conic at x,

• (b) there is an open ball  $U_\rho (x) \subset {\mathbb {R}}^n$ such that  $C_x(K) \subset C_z(K)$ whenever $z \in K \cap U_\rho (x)$.

• (c) there is an open ball  $U_\rho (x) \subset {\mathbb {R}}^n$ such that  $T_x(K) \subset T_z(K)$ whenever $z \in K \cap U_\rho (x)$.

Proof

$(a) \Rightarrow (b)$ Choose an open ball $U_\rho (x) \subset {\mathbb {R}}^n$ satisfying the equality (6), and let $z \in K \cap U_\rho (x)$. It is easy to see that, given a positive scalar $\delta \le \rho - \Vert x - z \Vert$, the open ball $U_\delta (z) \subset {\mathbb {R}}^n$ satisfies the inclusion $U_\delta (z) \subset U_\rho (x)$. Consequently, based on (3) and (6), we conclude:

$$\begin{aligned} C_x(K)&\subset C_z(C_x(K)) \\&= C_z(C_x(K) \cap U_\delta (z)) \\&= C_z(C_x(K) \cap U_\delta (z) \cap U_\rho (x)) \\&= C_z((C_x(K) \cap U_\rho (x)) \cap U_\delta (z)) \\&= C_z((K \cap U_\rho (x)) \cap U_\delta (z)) \\&= C_z(K \cap U_\delta (z)) = C_z(K). \end{aligned}$$

$(b) \Rightarrow (c)$ Choose a an open ball $U_\rho (x)$ satisfying condition (b). Then

$$\begin{aligned} T_x(K) = {\mathrm {cl\,}}C_x(K) \subset {\mathrm {cl\,}}C_z(K) = T_z(K) \ \ \text {whenever} \ \ z \in K \cap U_\rho (x). \end{aligned}$$

$(c) \Rightarrow (a)$ Since K is conic at any point from ${\mathrm {rint\,}}K$, we may assume that $x \in {\mathrm {rbd\,}}K$. Let an open ball $U_\rho (x) \subset {\mathbb {R}}^n$ satisfy condition (c). Chose any point $z \in {\mathrm {rbd\,}}K \cap U_\rho (x)$. Then $T_z(K) \ne {\mathrm {aff\,}}K$, implying that z, as an apex of $T_z(K)$, belongs to ${\mathrm {rbd\,}}T_z(K)$. We assert that $x \in {\mathrm {rbd\,}}T_z(K)$. Indeed, if x belonged to ${\mathrm {rint\,}}T_z(K)$, then, by Lemma 1, $z \in K \subset T_x(K) \subset {\mathrm {rint\,}}T_z(K)$, in contradiction with the inclusion $z \in {\mathrm {rbd\,}}T_z(K)$. Therefore, $[x, z] \subset {\mathrm {rbd\,}}T_z(K)$, which gives the inclusion $[x, z] \subset {\mathrm {rbd\,}}K$ (otherwise $(x, z) \subset {\mathrm {rint\,}}K$, again implying the impossible inclusion $x \in {\mathrm {rint\,}}T_z(K)$). Since z is an arbitrary point in ${\mathrm {rbd\,}}K \cap U_\rho (x)$, Lemma 5 shows that K is conic at x. $\square$

The sets of points of polyhedrality or conicity of a given convex set are studied in the papers [14, 21, 22].

3 Boundedly Polyhedral Sets

Various parts of the following Theorem 3 were proved by Bastiani (see [4, 5] for the case of convex cones and [3] for arbitrary convex sets) and Klee [14]. Similar proofs are given in [1, 11] (see also [20]).

Theorem 3

A closed convex set $K \subset {\mathbb {R}}^n$ is boundedly polyhedral if and only if any of the conditions below holds:

• (a) K is polyhedral at all points $x \in K$,

• (b) K is conic at all points $x \in K$,

• (c) all generated cones $C_x(K)$, $x \in K$, are closed. $\square$

A refinement of the above condition (a) was obtained in [14]: If X is a subset of a closed convex set $K \subset {\mathbb {R}}^n$ such that $K = {\mathrm {conv\,}}X$, then K is boundedly polyhedral if and only if K is polyhedral at all points of X. This assertion, combined with (1), implies the following corollary.

Corollary 3

A line-free closed convex set  $K \subset {\mathbb {R}}^n$ is boundedly polyhedral if and only if it is polyhedral at all points of  ${\mathrm {ext\,}}K \cup {\mathrm {extr\,}}K$. $\square$

Our Theorem 4 further refines Corollary 3 and sharpens Theorem 3.6 from [19] by dropping the condition on discreteness of ${\mathrm {ext\,}}K$.

Theorem 4

A line-free closed convex set $K \subset {\mathbb {R}}^n$ is boundedly polyhedral if and only if it is polyhedral at all points $x \in {\mathrm {ext\,}}K$.

Proof

The case ${\mathrm {dim\,}}K \le 1$ is trivial (K is either a singleton, a closed segment, or a closed halfline). Hence we may assume that ${\mathrm {dim\,}}K \ge 2$. Since the “only if” part is obvious, it remains to prove the “if” part.

So, let $K \subset {\mathbb {R}}^n$ be a line-free closed convex set which is polyhedral at all points $x \in {\mathrm {ext\,}}K$. Due to Corollary 3, it suffices to prove that K is polyhedral at all points of the set ${\mathrm {extr\,}}K \setminus {\mathrm {ext\,}}K$. Let $u \in {\mathrm {extr\,}}K \setminus {\mathrm {ext\,}}K$ and denote by $h_0$ the extreme halfline of K which contains u. Let v be the endpoint of $h_0$. Choose a point $z_0 \in h_0$ such that $u \in (v, z_0)$. Since $v \in {\mathrm {ext\,}}K$, the set K is polyhedral at v by the assumption. As stated in Lemma 2, the generated cone $C_v(K)$ is polyhedral. Obviously, $h_0$ is an extreme halfline of $C_v(K)$. Denote by $h_0, h_1, \dots , h_r$ all extreme halflines of $C_v(K)$. A combination of Lemmas 3 and 4 implies the existence of an open ball $U_\rho (v) \subset {\mathbb {R}}^n$ such that

$$\begin{aligned} K \cap U_\rho (v) = C_v(K) \cap U_\rho (v). \end{aligned}$$

Denote by $I_i$ the semiopen segment $h_i \cap U_\rho (v)$, $1 \le i \le r$.

The polyhedrality of $C_v(K)$ implies that all its extreme halflines $h_0, h_1, \dots , h_r$ are exposed. In other words, there are hyperplanes $H_0, \dots , H_r \subset {\mathbb {R}}^n$ such that

$$\begin{aligned} K \cap H_i = h_i \ \ \text {for all} \ \ 0 \le i \le r. \end{aligned}$$

Let L be an $(n - 2)$-dimensional plane in $H_0$ such that $L \cap h_0 = \{ z_0 \}$ ($H_0$ is the line containing $h_0$ and $L = \{ z_0 \}$ if $n = 2$). A continuity argument shows that $H_0$ can be slightly rotated about L such that its new position, say $H_0'$, meets every segment $I_i$ at a point $z_i$, $1 \le i \le r$. By the convexity of K, the polytope $Q = {\mathrm {conv\,}}\{ v, z_0, z_1, \dots , z_r \}$ is contained in K.

Let V be the closed halfspace determined by $H_0'$ and containing v. Then

$$\begin{aligned} h_i \cap V = [v, z_i] \ \ \text {for all} \ \ 0 \le i \le r, \end{aligned}$$

which gives the equality $Q = C_v(K) \cap V$. Therefore,

$$\begin{aligned} C_v(K) \cap V = Q \subset K \cap V \subset C_v(K) \cap V, \end{aligned}$$

which gives the equality $Q = K \cap V$. Since $u \in {\mathrm {int\,}}V$, there is an open ball $U_\delta (u) \subset V$. Thus

$$\begin{aligned} K \cap U_\delta (u) \subset K \cap V = Q, \end{aligned}$$

which shows that Q is a polyhedral neighborhood of u in K. So, K is polyhedral at u, as desired. $\square$

A combination of Lemma 3 and Corollary 2 implies that the set of extreme points of a boundedly polyhedral set is discrete and closed (this fact was already observed in [1, 3]). The following example shows that a line-free closed convex set $K \subset {\mathbb {R}}^n$ with discrete and closed set ${\mathrm {ext\,}}K$ is not necessarily boundedly polyhedral.

Example 2

On the circle $D = \{ (x, y, 0) : (x - 1)^2 + y^2 = 1 \}$ of the xy-plane of ${\mathbb {R}}^3$, choose the points $a = (0, 0, 1)$ and

$$\begin{aligned}&u_r = (1/r, \lambda _r, 0), \quad v_r = (1/r, -\lambda _r, 0), \ \ \text {where} \ \ \lambda _r = \sqrt{1 - (1 - 1/r)^2}, \\&b_r = a + r (u_i - a), \ \ c_r = a + r (v_r - a), \quad r \ge 1. \end{aligned}$$

Finally, let $E = \{ b_1, c_1, b_2, c_2, \dots \}$ and $K = {\mathrm {conv\,}}(\{ a \} \cup E) + h$, where h is the non-positive halfline of the z axis. It is easy to see that K is a closed convex set, with ${\mathrm {ext\,}}K = \{ a \} \cup E$. Clearly, ${\mathrm {ext\,}}K$ is a closed discrete set. Furthermore, K is conic but not polyhedral at a, while it is polyhedral at all points of E.

Our next result expands Theorem 4 to the case of convex sets with nontrivial lineality. We need the following lemma.

Lemma 6

Let a closed convex set  $K \subset {\mathbb {R}}^n$ be expressed as $K = (K \cap S) + {\mathrm {lin\,}}K$, where S is the orthogonal complement of  ${\mathrm {lin\,}}K$. Then K is boundedly polyhedral if and only if  $K \cap S$ is boundedly polyhedral.

Proof

Assume first that K is boundedly polyhedral, and let $P \subset {\mathbb {R}}^n$ be a polytope. By the assumption, the set $K \cap P$ is polytope. Consequently, the set $(K \cap P) \cap S$ is a polytope (possibly empty). Therefore, the equality $(K \cap S) \cap P = (K \cap P) \cap S$ implies that the intersection of $K \cap S$ and P is a polytope. Hence $K \cap S$ is boundedly polyhedral.

Conversely, assume that $K \cap S$ is boundedly polyhedral and choose a polytope $P \subset {\mathbb {R}}^n$. Denote by Q the orthogonal projection of P on S. Clearly, Q is a polytope and the set $P' = Q + {\mathrm {lin\,}}K$ is a polyhedron satisfying the inclusion $P \subset P'$. By the assumption, $(K \cap S) \cap Q$ is a polytope. This argument and the equality

$$\begin{aligned} K \cap P' = ((K \cap S) + {\mathrm {lin\,}}K) \cap (Q + {\mathrm {lin\,}}K) = ((K \cap S) \cap Q) + {\mathrm {lin\,}}K \end{aligned}$$

imply that $K \cap P'$ is a polyhedron. Consequently, $K \cap P = (K \cap P') \cap P$ is a polytope. Hence K is boundedly polyhedral. $\square$

Theorem 5

Let $K \subset {\mathbb {R}}^n$ be a closed convex set and X be a subset of K which meets every planar extreme face of K. Then K is boundedly polyhedral if and only K is polyhedral at all points of X.

Proof

Since the “only if” part obvious, it remains to prove the “if” part. So, let K be polyhedral at all points of X. If K is line-free, then all planar extreme faces of K are just its extreme points. In this case, ${\mathrm {ext\,}}K \subset X$ and the “if” part follows from Theorem 4.

Suppose that ${\mathrm {lin\,}}K \ne \{ o \}$ and express K in the form (2), where $K \cap S$ is a line-free closed convex set. Choose any point $u \in {\mathrm {ext\,}}(K \cap S)$ and consider the planar extreme face $F = u + {\mathrm {lin\,}}K$ of K. By the assumption, there is a point $v \in F \cap X$ such that K is polyhedral at v. Let Q be a polyhedral neighborhood of v in K. Choose an open ball $U_\rho (v) \subset {\mathbb {R}}^n$ satisfying the condition $K \cap U_\rho (v) \subset Q$. Put $Q' = Q + (u - v)$. Since $u - v \in {\mathrm {lin\,}}K$, one has $K = K + (u - v)$. Therefore,

$$\begin{aligned} Q' = Q + (u - v) \subset K + (u - v) = K. \end{aligned}$$

This argument and the inclusion

$$\begin{aligned} K \cap U_\rho (u)&= (K + (u - v)) \cap (U_\rho (v) + (u - v)) \\&= K \cap U_\rho (v) + (u - v) \\&\subset Q + (u - v) = Q' \end{aligned}$$

imply that $Q'$ is a polyhedral neighborhood of K at u. Consequently,

$$\begin{aligned} (K \cap S) \cap U_\rho (u) \subset Q' \cap S, \end{aligned}$$

which shows that $Q' \cap S$ is a polyhedral neighborhood of $K \cap S$ at u. Hence $K \cap S$ is polyhedral at u.

By Theorem 4, the set $K \cap S$ is boundedly polyhedral. Finally, Lemma 6 implies that the set K is boundedly polyhedral. $\square$

We will need one more lemma, which is similar in spirit to Lemma 3.2 from [1]. We recall that the union of all extreme faces of K of dimension at most one (which includes points, segments, halflines, and lines) is denoted ${\mathrm {ext}}_1 K$. Obviously, ${\mathrm {ext}}_1 K \subset {\mathrm {rbd\,}}K$ provided ${\mathrm {dim\,}}K \ge 2$.

Lemma 7

Let a line-free closed convex set $K \subset {\mathbb {R}}^n$ be conic but not polyhedral at a point $x \in {\mathrm {ext\,}}K$. Then there is a line segment $[x, z] \subset {\mathrm {cl\,}}({\mathrm {ext}}_1 K)$ such that K is not conic at any point $v \in (x, z)$.

Proof

Because K is conic but not polyhedral at x, one has ${\mathrm {dim\,}}K \ge 2$ (otherwise K would be polyhedral at x). Since K is conic at x, there is an open ball $U_\rho (x) \subset {\mathbb {R}}^n$ such that $[x, z] \subset {\mathrm {rbd\,}}K$ whenever $z \in {\mathrm {rbd\,}}K \cap U_\rho (x)$ (see Lemma 5). Consequently, the equality (6) holds. Corollary 1 shows that the line-free convex cone $C_x(K)$ is closed, and Lemma 2 implies that $C_x(K)$ is not polyhedral. So, $C_x(K)$ has infinitely many extreme halflines, say $h_1, h_2, \dots$, with common endpoint x. Clearly, all intersections $K \cap h_i$, $i \ge 1$, are 1-dimensional extreme faces of K, which are either segments or halflines (indeed, if $K \cap h_i = \{ x \}$, then $h_i \not \subset C_x(K)$). Let $[x, z_i) = h_i \cap U_\rho (x)$, $i \ge 1$. Then $[x, z_i] \subset {\mathrm {ext}}_1 K$ for all $i \ge 1$. Furthermore, $\Vert x - z_i \Vert = \rho$, $i \ge 1$, by the choice of $U_\rho (x)$. A compactness argument implies the existence of a subsequence of $z_1, z_2, \dots$ converging to a point $z \in K$. Without loss of generality, we may assume that $z_i \rightarrow z$. By a continuity argument, $[x, z] \subset {\mathrm {cl\,}}({\mathrm {ext}}_1 K)$ and $\Vert x - z \Vert = \rho$.

Choose any point $v \in (x, z)$ and denote by H the hyperplane through v orthogonal to (x, z). Since $\Vert x - v \Vert < \Vert x - z \Vert$, there is an index $r \ge 1$ such that every segment $[x, z_i]$, $i \ge r$, meets H at a point, say $v_i$. Since $\Vert v - v_i \Vert < \Vert z - z_i \Vert$, we conclude that $v_i \rightarrow v$ as $i \rightarrow \infty$.

Next, let $\delta > 0$. By the above argument, there is an index $s \ge r$ such that $\Vert v - v_t \Vert < \delta$ for all $t \ge s$. We assert that $K \cap [v, v_t \rangle = [v, v_t]$ whenever $t \ge s$. Indeed, assume the existence of an integer $t \ge s$ and a point $u \in (K \cap [v, v_t \rangle ) \setminus [v, v_t]$. Then $v_t$ belongs to the relative interior of the quadrilateral $Q = {\mathrm {conv\,}}\{ x, v, u, z_t \} \subset K$. Consequently, the extreme face of K generated by $v_t$ should contain Q. The latter is impossible because of the choice of $v_t$ in the 1-dimensional extreme face $K \cap [x, z_t \rangle$ of K. Hence $K \cap [v, v_t \rangle = [v, v_t]$ for all $t \ge s$.

Finally, choose a point $w \in [v, v_t \rangle \setminus [v, v_t]$ such that $\Vert v - w \Vert < \delta$. Then

$$\begin{aligned} w \in (C_v(K) \cap U_\delta ) \setminus (K \cap U_\delta ), \end{aligned}$$

implying that

$$\begin{aligned} K \cap U_\delta (v) \ne C_v(K) \cap U_\delta (v) \ \ \text {for all} \ \ \delta > 0. \end{aligned}$$

Hence K is not conic at v, as desired. $\square$

The next example shows that the conicity of a line-free closed convex set $K \subset {\mathbb {R}}^n$ at every point of ${\mathrm {ext\,}}K$ is not sufficient for its bounded polyhedrality (compare with Theorem 4).

Example 3

On the circle $D = \{ (x, y, 0) : (x - 1)^2 + y^2 = 1 \}$ of the xy-plane in ${\mathbb {R}}^3$, consider the points

$$\begin{aligned} u_r = (1/r, y_r, 0), \quad v_r = (1/r, -y_r, 0), \ \ \text {where} \ \ y_r = \sqrt{1 - (1 - 1/r)^2}, \ \ r \ge 1. \end{aligned}$$

Let $E = \{ u_1, v_1, u_2, v_2, \dots \}$ and $K = {\mathrm {conv\,}}(\{ a, c \} \cup E)$, where $a = (0, 0, 1)$ and $c = (0, 0, -1)$. It is easy to see that K is a convex body, with ${\mathrm {ext\,}}K = \{ a, c \} \cup E$. The set ${\mathrm {ext\,}}K$ is not closed because $o = (0, 0, 0) \in {\mathrm {cl\,}}({\mathrm {ext\,}}K) \setminus {\mathrm {ext\,}}K$. Furthermore, K is polyhedral at any point of $K \setminus [a, c]$ and is conic at any point of $K \setminus (a, c)$.

Theorem 6

A line-free closed convex set  $K \subset {\mathbb {R}}^n$ is boundedly polyhedral if and only if  K is conic at all points of  ${\mathrm {cl\,}}({\mathrm {ext}}_1 K)$.

Proof

Since the “only if” part is obvious, it suffices to prove the “if” part. So, let a line-free closed convex set  $K \subset {\mathbb {R}}^n$ be conic at all points of ${\mathrm {cl\,}}({\mathrm {ext}}_1 K)$. Assume, for contradiction, that K is not boundedly polyhedral. According to Theorem 4, there is a point $x \in {\mathrm {ext\,}}K$ such that K is not polyhedral at x. By the hypothesis, K is conic at x (because ${\mathrm {ext\,}}K \subset {\mathrm {ext}}_1 K$). Lemma 7 implies the existence of a segment $[x, z] \subset {\mathrm {cl\,}}({\mathrm {ext}}_1 K)$ such that K is not conic at any point $v \in (x, z)$, contrary to the assumption. Hence K should be boundedly polyhedral. $\square$

Corollary 4

A line-free closed convex set  $K \subset {\mathbb {R}}^3$ is boundedly polyhedral if and only if all generated cones $C_x(K)$, $x \in {\mathrm {cl\,}}({\mathrm {ext}}_1 K)$, are closed.

Proof

Since the case ${\mathrm {dim\,}}K \le 2$ is obvious, we may suppose that ${\mathrm {dim\,}}K = 3$. Assuming that K is not boundedly polyhedral and repeating the proof of Lemma 7, we conclude that every point $v_i$ of the closed convex set $M = K \cap H$ belongs to ${\mathrm {ext\,}}M$ and $v_i \rightarrow v \in {\mathrm {cl\,}}({\mathrm {ext}}_1 K)$ as $i \rightarrow \infty$. In this case (since ${\mathrm {dim\,}}M = 2$), the generated cone $C_v(M)$ is not closed, which implies that the cone $C_v(K)$ is not closed as well. $\square$

Problem 1

Does the assertion of Corollary 4 hold for all $n \ge 3$?