Convexity/The convex hull

From Wikibooks, open books for an open world
Jump to: navigation, search
The convex hull (blue) of a set (red).

Definition[edit]

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).