Why does a closed convex set contain lines if and only it has no extreme points?

Question

Let $A\subset\mathbb R^n$ be a closed and convex. A points $x\in A$ is said to be an extreme point if it cannot be represented as a nontrivial convex combination of points in $A$. Let $\operatorname{ext}A$ denote the set of extreme points of $A$.

I've stumbled upon the observation that "$A$ contains lines if and only if it has no extreme points" (page 37, remark 1, in Hug and Weil (2010), pdf can be found here).

I can see that if $A$ contains a line $L$, then it cannot have extreme points. Indeed, given any $x\notin L$, then the (closed) convex closure of $\{x\}\cup L$ must equal everything between $L$ and the line parallel to $L$ intersecting $x$, and such set has no extreme points. Geometrically, this amounts to the following construction:

$\qquad\qquad\qquad$

However, I'm not sure how to proceed for the other direction. How do I prove that if $A$ contains no lines, then there must be at least an extreme point (or equivalently, that the absence of extreme points implies that at least one line is contained in $A$)?

Answer 1

$A$ must be assumed nonempty of course. Then we can use induction on the dimension.

In $\mathbb{R}^1$, a nonempty closed convex set $A$ that contains no line has one of the forms $(-\infty, a]$, $[a, +\infty)$, or $[a,b]$ (with $a \leqslant b$), and for all these $a$ is an extreme point of $A$.

For the induction step, let $x \in A$ and consider an arbitrary line $L$ passing through $x$. Since $L \not\subset A$ there is a point $y \in L\setminus A$. Let $s = \max \{ t \in [0,1] : x + t(y-x) \in A\}$ and $z = x + s(y-x)$. Then there is a supporting hyperplane for $A$ passing through $z$. This is given by $$ H = \{\xi : \langle \xi, \eta\rangle = \langle z, \eta\rangle\}$$ for some $\eta \in \mathbb{R}^n$ with $\langle \eta, \eta\rangle = 1$. We can without loss of generality assume that $\langle \xi, \eta\rangle \leqslant \langle z, \eta\rangle$ for all $\xi \in A$.

Now $A_H = A \cap H$ is a closed convex set in the hyperplane $H$ (which we can identify with $\mathbb{R}^{n-1}$) that contains no line and is nonempty (for $z \in A_H$). By the induction hypothesis, $A_H$ has extreme points. But an extreme point of $A_H$ is also an extreme point of $A$, for if a point $p$ of $A_H$ is represented as a convex combination of two points of $A$, then these two points must both lie in $A_H$. Thus $A$ has extreme points.

Answer 2

Here's a slight rewording of the other answer.

I want to prove that a closed, convex, nonempty $A\subset\mathbb R^n$ which contains no lines, always contains at least an extreme points.

The $\mathbb R^1$ case is trivial: the only possible $A$ are finite closed intervals or infinite segments of the form $[a,\infty)$ and $(-\infty,a]$. Let us, therefore, assume that the statement is true for $A\subset\mathbb R^{n-1}$.

Let $x\in A$ be an arbitrary point, and let $L$ be some line passing through $x$. Thus $x\in L$, and by hypothesis $L\not\subset A$. There will then be some $y\in L\setminus A$. Let then $z\in L\cap \operatorname{conv}(\{x,y\})$ be an element on the boundary of $A$, let $H$ be the supporting hyperplane for $A$ passing through $z$, and consider the set $A_H\equiv A\cap H$. Here's a representation of this construction in $\mathbb R^2$:

In this simple case, $H$ must be a line and thus $A_H\subset\mathbb R^1$ contains an extreme point as per the induction hypothesis (in this particular case $A_H=\{z\}$). More generally, $A_H$ will be closed, convex, nonempty subset of $\mathbb R^{n-1}$, and thus contain extreme points.

Now it only remains to prove that an extreme point of $A_H$ is also an extreme point for $A$. In other words, we must prove that if $p\in A_H$ then $p\notin \operatorname{conv}(A\setminus A_H)$. For the purpose, we remember that $A_H$ is defined as the intersection between $A$ and a hyperplane, which means that there is some $\eta\in\mathbb R^n$ and $\alpha\in\mathbb R$ such that, defining $f(\xi)\equiv \langle \eta,\xi\rangle$, we have $f(\xi)\le \alpha$ for all $\xi\in A$, and $f(\xi)=\alpha$ for all $\xi\in A_H$.

But then, if $p\in A_H$ were a convex combination of elements of $A$, $p=\sum_k \lambda_k a_k$ with $a_k\in A, \sum_k\lambda_k=1, \lambda_k\ge0$, then $$\sum_k \lambda_k f(a_k) = f(p)= \alpha,$$ which is only possible if $f(a_k)=\alpha$ for all $k$, i.e. if $a_k\in A_H$.