In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

Convex hulls of open sets are open, and convex hulls of compact sets are compact. Every compact convex set is the convex hull of its extreme points. The convex hull operator is an example of a closure operator, and every antimatroid can be represented by applying this closure operator to finite sets of points. The algorithmic problems of finding the convex hull of a finite set of points in the plane or other low-dimensional Euclidean spaces, and its dual problem of intersecting half-spaces, are fundamental problems of computational geometry. They can be solved in time ${\displaystyle O(n\log n)}$ for two or three dimensional point sets, and in time matching the worst-case output complexity given by the upper bound theorem in higher dimensions.

As well as for finite point sets, convex hulls have also been studied for simple polygons, Brownian motion, space curves, and epigraphs of functions. Convex hulls have wide applications in mathematics, statistics, combinatorial optimization, economics, geometric modeling, and ethology. Related structures include the orthogonal convex hull, convex layers, Delaunay triangulation and Voronoi diagram, and convex skull.

A set of points in a Euclidean space is defined to be convex if it contains the line segments connecting each pair of its points. The convex hull of a given set ${\displaystyle X}$ may be defined as

For bounded sets in the Euclidean plane, not all on one line, the boundary of the convex hull is the simple closed curve with minimum perimeter containing ${\displaystyle X}$. One may imagine stretching a rubber band so that it surrounds the entire set ${\displaystyle S}$ and then releasing it, allowing it to contract; when it becomes taut, it encloses the convex hull of ${\displaystyle S}$. This formulation does not immediately generalize to higher dimensions: for a finite set of points in three-dimensional space, a neighborhood of a spanning tree of the points encloses them with arbitrarily small surface area, smaller than the surface area of the convex hull. However, in higher dimensions, variants of the obstacle problem of finding a minimum-energy surface above a given shape can have the convex hull as their solution.

For objects in three dimensions, the first definition states that the convex hull is the smallest possible convex bounding volume of the objects. The definition using intersections of convex sets may be extended to non-Euclidean geometry, and the definition using convex combinations may be extended from Euclidean spaces to arbitrary real vector spaces or affine spaces; convex hulls may also be generalized in a more abstract way, to oriented matroids.

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.

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.