1. The convex hull of a set

Let $S_0$ be any subset of R$^n$, convex or not. For example, $S_0$ could be a subset of R$^2$ with an indentation, or it could even consist of finitely many points. The convex hull of $S_0$ is the smallest convex set containing $S_0$, which does exist; see Figure for examples.

Proposition 2.1. For any subset $S_0$ of R$^n$, there is a convex set $C$ containing $S_0$ in R$^n$ that is smallest, in the sense that $C$ is contained in all other convex sets that contain $S_0$.

Proof. Let $C$ be the intersection of all convex sets containing $S_0$. Then $C$ is clearly contained in all convex sets that contain $S_0$, so the only question is whether $C$ itself is convex. But it is, because if $P$ and $Q$ are two points in $C$, then $P$ and $Q$ are in each convex set containing $S_0$, so all of the segment $\overline {PQ}$ is, and so $\overline {PQ}$ is all in the intersection of those convex sets, which is $C$.

Definition. For any subset $S_0$ of R$^n$, the smallest convex set containing R$^n$ is the convex hull of $S_0$.

Figure: Constructing convex hulls

.9book/06dir/hulls.eps