Convexity/The convex hull
Definition[edit | edit source]
The convex hull, also known as the convex envelope, of a set X is the smallest convex set of which X is a subset. Formally,
Definition: The convex hull H(X) of a set X is the intersection of all convex sets of which X is a subset.
If X is convex, then obviously H(X) = X, since X is a subset of itself. Conversely, if H(X) = X, X is obviously convex.
Theorem: If X is closed and bounded, so is H(X).
Theorem: H(X) is the union of all straight lines joining all pairs of points in X (where the line includes the end-points).
Proof: Let A, B be any two points in X. They are also in any convex set Y containing X. The line joining them must also lie within Y hence it must lie within the intersection of all convex sets containing X, i.e. within H(X). Thus the union of all such straight lines is a subset of H(X).