= Convex hull
{title2=$\operatorname{conv}(S)$}
{wiki}
The <convex hull> of a <set> consists of every finite <convex combination> of its points. It collects all choices obtainable by mixing the original choices with nonnegative weights summing to one. For $S$ in a real <vector space>,
$$
\operatorname{conv}(S)=\left\{\sum_{i=1}^m\lambda_i s_i:s_i\in S,\ m\geq1,\ \lambda_i\geq0,\ \sum_{i=1}^m\lambda_i=1\right\}.
$$
Equivalently this is the smallest <convex set> containing $S$. Mixing two already mixed points produces another finite <convex combination>, so the displayed <set> is convex; every <convex set> containing $S$ must contain all these mixtures.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§2.1.4, printed p. 24: convex hull and smallest containing convex set]{ref}
In an original planar example, take four points $A=(0,0)$, $B=(4,0)$, $C=(3,3)$, $D=(0,2)$ and four additional samples $(1,1)$, $(2,1.7)$, $(3,0.5)$, $(1,0.5)$. Their <convex hull> is the filled <convex polygon> $ABCD$, including its <boundary>. None of the samples is $p=(2,1)$, but
$$
p=\frac5{12}A+\frac14B+\frac13C.
$$
The <coefficients> are nonnegative and sum to one, providing an explicit membership certificate. Geometrically, first form $U=(3/2,0)=\tfrac58A+\tfrac38B$ on the <line segment> $AB$, then mix $p=\tfrac23U+\tfrac13C$. The additional interior samples do not enlarge the <convex hull>.
\Image[/convex-hull-point-cloud-mixture.png]
{title=A finite <set> gains new points through <convex combinations>}
{description=Original eight-point planar example. The blue <convex polygon> is the <convex hull>; the orange star $p=(2,1)$ is absent from the original samples. Mixing on $AB$ produces $U$, and mixing $U$ with $C$ produces $p$ using exactly three original points.}
For a finite nonempty $S\subset\mathbb R^d$, the <convex hull> is the image of a <probability simplex> of weights under the <linear map> $\lambda\mapsto\sum_i\lambda_i s_i$. The <probability simplex> is a <compact set>, and the map is <continuous>, so this <convex hull> is compact and closed. A one-point input stays one point; a collinear input stays in a <line segment>. Filling the <convex hull> does not necessarily produce a full-dimensional region.
The construction is useful whenever mixtures preserve the intended meaning of a choice. Mixing resource-allocation <vectors>, for example, interpolates their coordinate requirements. The <convex hull> describes the resulting <feasible region>. A coordinate-wise box can admit combinations that no mixture produces, as the outside-point certificate in <linear optimization on a convex hull> shows.
Back to article page
