Convex hull ($\mathrm{conv}(S)$)

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,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.^[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)$, butThe coefficients are nonnegative and sum to one, providing an explicit membership certificate. Geometrically, first form $U=(3/2,0)=\frac{5}{8}A+\frac{3}{8}B$ on the line segment $AB$, then mix $p=\frac{2}{3}U+\frac{1}{3}C$. The additional interior samples do not enlarge the convex hull.

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.

Start from a nondegenerate tetrahedron and insert remaining points one at a time. Discard a point inside the current convex polyhedron; otherwise replace faces visible from it by the cone from that point to the horizon of a convex polyhedron. Scanning every current face gives $O(n^2)$ worst-case time complexity and $O(n)$ current-hull storage in three dimensions. Coplanar input requires a separate degeneracy policy.

Every set of at least $d+2$ points in ${\mathbb{R}}^d$ can be partitioned into two nonempty parts with intersecting convex hulls. To see this, take a nonzero affine dependence on $d+2$ of its points. Its positive and negative coefficient sums have the same magnitude $L>0$. Dividing by $L$ expresses one point as a convex combination of the positive-coefficient points and also as a convex combination of the negative-coefficient points. Distribute zero-coefficient and remaining points arbitrarily between the parts. This theorem obstructs arbitrary labels for affine linear classifiers.

In a Banach space, the closed convex hull of a compact set is compact in the norm topology. Given $\epsilon >0$, choose a finite $\epsilon$-net $\{y_i\}$ for $K$. Every convex combination of points of $K$ is within $\epsilon$ in norm of $\mathrm{conv}\{y_i\}$, by replacing its terms by their approximating $y_i$. This finite-dimensional compact convex set has a finite $\epsilon$-net, giving a finite $2\epsilon$-net for $\mathrm{conv}K$. Its closure is therefore totally bounded and complete, hence compact. Completeness of the ambient space is used at this last step.

The lower boundary of the convex hull of points in the plane: the portion visible from points sufficiently far in the negative vertical direction. Sorting its vertices by horizontal coordinate gives a chain with nondecreasing edge slopes; collinear interior vertices can be omitted.

A linear functional cannot exceed its best original value by mixing. For a finite nonempty set $S$ and $x={\sum }_i{\lambda }_i{s}_i$ in its convex hull,Every original point is itself in the convex hull, so equality between the two maxima follows. Moreover, a mixture attains the maximum exactly when all its positive weights are assigned to maximizing original points. Multiple maximizers can therefore produce a whole line segment or a higher-dimensional region of equally good choices.

For the eight samples above, use the linear functional $f(x,y)=x+y$. Its largest sample value is $f(C)=6$, and $C$ is the only maximizing sample. Thus the unique maximum over the whole convex polygon is also at $C$. The line $x+y=6$ is a supporting line: every point of the convex hull lies in the half-space $x+y\le 6$, and $C$ touches its boundary.

The point $q=(3.8,2.5)$ passes the coordinate-wise bounds $0\le x\le 4$, $0\le y\le 3$, but $f(q)=6.3>6$. This single inequality certifies that $q$ is outside the convex hull. A weighted mixture could not have a larger linear functional value than all its ingredients.

This explains a basic feature of linear programming: searching all mixtures of finitely many candidate vectors cannot improve the objective beyond the best candidate, though mixing equally good candidates can give more optimal choices. The conclusion depends on linearity. For the concave function $g(x,y)=-(x-2{)}^2-(y-1{)}^2$, the new point $p=(2,1)$ instead attains zero, strictly above its value at every original sample. A nonlinear objective can favor a mixture.

The smallest closed convex set containing a set $C$, equivalently the closure of its convex hull in the specified topology. The topology must be stated: the norm topology, weak topology and weak-star topology need not give the same closure for an arbitrary set.

Even a bounded infinite input need not have a closed convex hull. In the real line, let $S=\{1/n:n\ge 1\}$. Every finite convex combination of these positive points is positive, so zero is absent. Conversely, any $x\in (0,1]$ lies between some $1/n$ and $1$, and is their convex combination. HenceThe closed convex hull adds the missing limit point zero. For the finite eight-point example in convex hull, the convex hull is already closed, so taking the closed convex hull adds nothing.

Every point in the convex hull of a subset of ${\mathbb{R}}^d$ is a convex combination of at most $d+1$ points of that subset. Thus in the plane three ingredients always suffice, however many samples were supplied. The representation of $p=(2,1)$ in convex hull illustrates this bound. Two ingredients need not suffice: the centroid of a triangle with only its three vertices as input is on none of their three pairwise line segments.

A short proof outline removes redundant ingredients. With more than $d+1$ points, the augmented vectors $(s_i,1)$ are linearly dependent. A dependence lets the weights vary while preserving both their sum and the represented point. Move along it until one positive weight first becomes zero; all weights stay nonnegative. Repeating leaves at most $d+1$ positive weights.

In his 1911 paper, Constantin Carathéodory used convex geometry to investigate the possible Fourier coefficients of positive harmonic functions. Its introduction interprets convex mixtures through the center of mass, connecting finite-dimensional geometry to constraints on a function's coefficients.^[ref]

In an $N$-dimensional real vector space, each member of a conic hull has a representation using at most $N$ generators. To prove it, take a finite positive-coefficient representation with more than $N$ terms. Its generators are linearly dependent, say ${\sum }_j{\mu }_j{s}_j=0$, with some ${\mu }_j>0$ after reversing the relation if necessary. Subtract $t{\mu }_j$ from each coefficient, taking $t={\min }_{{\mu }_j>0}{\lambda }_j/{\mu }_j$. All coefficients stay nonnegative and at least one vanishes. Iterate. The bound differs from the $N+1$ bound for a convex hull because the coefficient sum is unrestricted.