Convex hull

3D convex hull of 120 point cloud

It is not obvious that the first definition makes sense: why should there exist a unique minimal convex set containing ${\displaystyle X}$, for every ${\displaystyle X}$? However, the second definition, the intersection of all convex sets containing ${\displaystyle X}$, is well-defined. It is a subset of every other convex set ${\displaystyle Y}$ that contains ${\displaystyle X}$, because ${\displaystyle Y}$ is included among the sets being intersected. Thus, it is exactly the unique minimal convex set containing ${\displaystyle X}$. Therefore, the first two definitions are equivalent.[1]

Each convex set containing ${\displaystyle X}$ must (by the assumption that it is convex) contain all convex combinations of points in ${\displaystyle X}$, so the set of all convex combinations is contained in the intersection of all convex sets containing ${\displaystyle X}$. Conversely, the set of all convex combinations is itself a convex set containing ${\displaystyle X}$, so it also contains the intersection of all convex sets containing ${\displaystyle X}$, and therefore the second and third definitions are equivalent.[6]

In fact, according to Carathéodory's theorem, if ${\displaystyle X}$ is a subset of a ${\displaystyle d}$-dimensional Euclidean space, every convex combination of finitely many points from ${\displaystyle X}$ is also a convex combination of at most ${\displaystyle d+1}$ points in ${\displaystyle X}$. The set of convex combinations of a ${\displaystyle (d+1)}$-tuple of points is a simplex; in the plane it is a triangle and in three-dimensional space it is a tetrahedron. Therefore, every convex combination of points of ${\displaystyle X}$ belongs to a simplex whose vertices belong to ${\displaystyle X}$, and the third and fourth definitions are equivalent.[6]

In two dimensions, the convex hull is sometimes partitioned into two parts, the upper hull and the lower hull, stretching between the leftmost and rightmost points of the hull. More generally, for convex hulls in any dimension, one can partition the boundary of the hull into upward-facing points (points for which an upward ray is disjoint from the hull), downward-facing points, and extreme points. For three-dimensional hulls, the upward-facing and downward-facing parts of the boundary form topological disks.[7]

The closed convex hull of a set is the closure of the convex hull, and the open convex hull is the interior (or in some sources the relative interior) of the convex hull.[8]

The closed convex hull of ${\displaystyle X}$ is the intersection of all closed half-spaces containing ${\displaystyle X}$. If the convex hull of ${\displaystyle X}$ is already a closed set itself (as happens, for instance, if ${\displaystyle X}$ is a finite set or more generally a compact set), then it equals the closed convex hull. However, an intersection of closed half-spaces is itself closed, so when a convex hull is not closed it cannot be represented in this way.[9]

If the open convex hull of a set ${\displaystyle X}$ is ${\displaystyle d}$-dimensional, then every point of the hull belongs to an open convex hull of at most ${\displaystyle 2d}$ points of ${\displaystyle X}$. The sets of vertices of a square, regular octahedron, or higher-dimensional cross-polytope provide examples where exactly ${\displaystyle 2d}$ points are needed.[10]

The witch of Agnesi. The points on or above the red curve provide an example of a closed set whose convex hull is open (the open upper half-plane).

Topologically, the convex hull of an open set is always itself open, and the convex hull of a compact set is always itself compact. However, there exist closed sets for which the convex hull is not closed.[11] For instance, the closed set

${\displaystyle \left\{(x,y)\mathop {\bigg |} y\geq {\frac {1}{1+x^{2}}}\right\}}$

(the set of points that lie on or above the witch of Agnesi) has the open upper half-plane as its convex hull.[12]

The compactness of convex hulls of compact sets, in finite-dimensional Euclidean spaces, is generalized by the Krein–Smulian theorem, according to which the closed convex hull of a weakly compact subset of a Banach space (a subset that is compact under the weak topology) is weakly compact.[13]

An extreme point of a convex set is a point in the set that does not lie on any open line segment between any other two points of the same set. For a convex hull, every extreme point must be part of the given set, because otherwise it cannot be formed as a convex combination of given points. According to the Krein–Milman theorem, every compact convex set in a Euclidean space (or more generally in a locally convex topological vector space) is the convex hull of its extreme points.[14] However, this may not be true for convex sets that are not compact; for instance, the whole Euclidean plane and the open unit ball are both convex, but neither one has any extreme points. Choquet theory extends this theory from finite convex combinations of extreme points to infinite combinations (integrals) in more general spaces.[15]

The convex-hull operator has the characteristic properties of a closure operator:[16]

• It is extensive, meaning that the convex hull of every set ${\displaystyle X}$ is a superset of ${\displaystyle X}$.
• It is non-decreasing, meaning that, for every two sets ${\displaystyle X}$ and Y with ${\displaystyle X\subseteq Y}$, the convex hull of ${\displaystyle X}$ is a subset of the convex hull of ${\displaystyle Y}$.
• It is idempotent, meaning that for every ${\displaystyle X}$, the convex hull of the convex hull of ${\displaystyle X}$ is the same as the convex hull of ${\displaystyle X}$.

When applied to a finite set of points, this is the closure operator of an antimatroid, the shelling antimatroid of the point set. Every antimatroid can be represented in this way by convex hulls of points in a Euclidean space of high-enough dimension.[17]

The operations of constructing the convex hull and taking the Minkowski sum commute with each other, in the sense that the Minkowski sum of convex hulls of sets gives the same result as the convex hull of the Minkowski sum of the same sets. This provides a step towards the Shapley–Folkman theorem bounding the distance of a Minkowski sum from its convex hull.[18]

The projective dual operation to constructing the convex hull of a set of points is constructing the intersection of a family of closed halfspaces that all contain the origin (or any other designated point).[19]

Convex hull of points in the plane

The convex hull of a finite point set ${\displaystyle S\subset \mathbb {R} ^{d}}$ forms a convex polygon when ${\displaystyle d=2}$, or more generally a convex polytope in ${\displaystyle \mathbb {R} ^{d}}$. Each extreme point of the hull is called a vertex, and (by the Krein–Milman theorem) every convex polytope is the convex hull of its vertices. It is the unique convex polytope whose vertices belong to ${\displaystyle S}$ and that encloses all of ${\displaystyle S}$.[2] For sets of points in general position, the convex hull is a simplicial polytope.[20]

According to the upper bound theorem, the number of faces of the convex hull of ${\displaystyle n}$ points in ${\displaystyle d}$-dimensional Euclidean space is ${\displaystyle O(n^{\lfloor d/2\rfloor })}$.[21] In particular, in two and three dimensions the number of faces is at most linear in ${\displaystyle n}$.[22]

Convex hull ( in blue and yellow) of a simple polygon (in blue)

The convex hull of a simple polygon encloses the given polygon and is partitioned by it into regions, one of which is the polygon itself. The other regions, bounded by a polygonal chain of the polygon and a single convex hull edge, are called pockets. Computing the same decomposition recursively for each pocket forms a hierarchical description of a given polygon called its convex differences tree.[23] Reflecting a pocket across its convex hull edge expands the given simple polygon into a polygon with the same perimeter and larger area, and the Erdős–Nagy theorem states that this expansion process eventually terminates.[24]

The curve generated by Brownian motion in the plane, at any fixed time, has probability 1 of having a convex hull whose boundary forms a continuously differentiable curve. However, for any angle ${\displaystyle \theta }$ in the range ${\displaystyle \pi /2<\theta <\pi }$, there will be times during the Brownian motion where the moving particle touches the boundary of the convex hull at a point of angle ${\displaystyle \theta }$. The Hausdorff dimension of this set of exceptional times is (with high probability) ${\displaystyle 1-\pi /2\theta }$.[25]

An oloid, the convex hull of two circles in 3d space

For the convex hull of a space curve or finite set of space curves in general position in three-dimensional space, the parts of the boundary away from the curves are developable and ruled surfaces.[26] Examples include the oloid, the convex hull of two circles in perpendicular planes, each passing through the other's center,[27] the sphericon, the convex hull of two semicircles in perpendicular planes with a common center, and D-forms, the convex shapes obtained from Alexandrov's uniqueness theorem for a surface formed by gluing together two planar convex sets of equal perimeter.[28]

The convex hull or lower convex envelope of a function ${\displaystyle f}$ on a real vector space is the function whose epigraph is the lower convex hull of the epigraph of ${\displaystyle f}$. It is the unique maximal convex function majorized by ${\displaystyle f}$.[29] The definition can be extended to the convex hull of a set of functions (obtained from the convex hull of the union of their epigraphs, or equivalently from their pointwise minimum) and, in this form, is dual to the convex conjugate operation.[30]

Partition of seven points into three subsets with intersecting convex hulls, guaranteed to exist for any seven points in the plane by Tverberg's theorem

Newton polygons of univariate polynomials and Newton polytopes of multivariate polynomials are convex hulls of points derived from the exponents of the terms in the polynomial, and can be used to analyze the asymptotic behavior of the polynomial and the valuations of its roots.[48] Convex hulls and polynomials also come together in the Gauss–Lucas theorem, according to which the roots of the derivative of a polynomial all lie within the convex hull of the roots of the polynomial.[49]

In spectral analysis, the numerical range of a normal matrix is the convex hull of its eigenvalues.[50] The Russo–Dye theorem describes the convex hulls of unitary elements in a C*-algebra.[51] In discrete geometry, both Radon's theorem and Tverberg's theorem concern the existence of partitions of point sets into subsets with intersecting convex hulls.[52]

The definitions of a convex set as containing line segments between its points, and of a convex hull as the intersection of all convex supersets, apply to hyperbolic spaces as well as to Euclidean spaces. However, in hyperbolic space, it is also possible to consider the convex hulls of sets of ideal points, points that do not belong to the hyperbolic space itself but lie on the boundary of a model of that space. The boundaries of convex hulls of ideal points of three-dimensional hyperbolic space are analogous to ruled surfaces in Euclidean space, and their metric properties play an important role in the geometrization conjecture in low-dimensional topology.[53] Hyperbolic convex hulls have also been used as part of the calculation of canonical triangulations of hyperbolic manifolds, and applied to determine the equivalence of knots.[54]

See also the section on Brownian motion for the application of convex hulls to this subject, and the section on space curves for their application to the theory of developable surfaces.

A bagplot. The outer shaded region is the convex hull, and the inner shaded region is the 50% Tukey depth contour.

In robust statistics, the convex hull provides one of the key components of a bagplot, a method for visualizing the spread of two-dimensional sample points. The contours of Tukey depth form a nested family of convex sets, with the convex hull outermost, and the bagplot also displays another polygon from this nested family, the contour of 50% depth.[55]

In statistical decision theory, the risk set of a randomized decision rule is the convex hull of the risk points of its underlying deterministic decision rules.[56]

In combinatorial optimization and polyhedral combinatorics, central objects of study are the convex hulls of indicator vectors of solutions to a combinatorial problem. If the facets of these polytopes can be found, describing the polytopes as intersections of halfspaces, then algorithms based on linear programming can be used to find optimal solutions.[57] In multi-objective optimization, a different type of convex hull is also used, the convex hull of the weight vectors of solutions. One can maximize any quasiconvex combination of weights by finding and checking each convex hull vertex, often more efficiently than checking all possible solutions.[58]

In the Arrow–Debreu model of general economic equilibrium, agents are assumed to have convex budget sets and convex preferences. These assumptions of convexity in economics can be used to prove the existence of an equilibrium. When actual economic data is non-convex, it can be made convex by taking convex hulls. The Shapley–Folkman theorem can be used to show that, for large markets, this approximation is accurate, and leads to a "quasi-equilibrium" for the original non-convex market.[59]

In geometric modeling, one of the key properties of a Bézier curve is that it lies within the convex hull of its control points. This so-called "convex hull property" can be used, for instance, in quickly detecting intersections of these curves.[60]

In the geometry of boat and ship design, chain girth is a measurement of the size of a sailing vessel, defined using the convex hull of a cross-section of the hull of the vessel. It differs from the skin girth, the perimeter of the cross-section itself, except for boats and ships that have a convex hull.[61]

The convex hull is commonly known as the minimum convex polygon in ethology, the study of animal behavior, where it is a classic, though perhaps simplistic, approach in estimating an animal's home range based on points where the animal has been observed.[62] Outliers can make the minimum convex polygon excessively large, which has motivated relaxed approaches that contain only a subset of the observations, for instance by choosing one of the convex layers that is close to a target percentage of the samples,[63] or in the local convex hull method by combining convex hulls of neighborhoods of points.[64]

In quantum physics, the state space of any quantum system — the set of all ways the system can be prepared — is a convex hull whose extreme points are positive-semidefinite operators known as pure states and whose interior points are called mixed states.[65] The Schrödinger–HJW theorem proves that any mixed state can in fact be written as a convex combination of pure states in multiple ways.[66]