The convex hull of the red set is the blue and red
convex set.
In mathematics, the convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X. For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around X.^{[1]}
Formally, the convex hull may be defined as the intersection of all convex sets containing X or as the set of all convex combinations of points in X. With the latter definition, convex hulls may be extended from Euclidean spaces to arbitrary real vector spaces; they may also be generalized further, to oriented matroids.
The algorithmic problem of finding the convex hull of a finite set of points in the plane or other lowdimensional Euclidean spaces is one of the fundamental problems of computational geometry.
Contents

Definitions 1

Convex hull of a finite point set 2

Computation of convex hulls 3

Minkowski addition and convex hulls 4

Relations to other structures 5

Applications 6

See also 7

Notes 8

References 9

External links 10
Definitions
A set of points is defined to be convex if it contains the line segments connecting each pair of its points. The convex hull of a given set X may be defined as

The (unique) minimal convex set containing X

The intersection of all convex sets containing X

The set of all convex combinations of points in X.

The union of all simplices with vertices in X.
It is not obvious that the first definition makes sense: why should there exist a unique minimal convex set containing X, for every X? However, the second definition, the intersection of all convex sets containing X is welldefined, and it is a subset of every other convex set Y that contains X, because Y is included among the sets being intersected. Thus, it is exactly the unique minimal convex set containing X. Each convex set containing X must (by the assumption that it is convex) contain all convex combinations of points in X, so the set of all convex combinations is contained in the intersection of all convex sets containing X. Conversely, the set of all convex combinations is itself a convex set containing X, so it also contains the intersection of all convex sets containing X, and therefore the sets given by these two definitions must be equal. In fact, according to Carathéodory's theorem, if X is a subset of an Ndimensional vector space, convex combinations of at most N + 1 points are sufficient in the definition above. Therefore, the convex hull of a set X of three or more points in the plane is the union of all the triangles determined by triples of points from X, and more generally in Ndimensional space the convex hull is the union of the simplices determined by at most N + 1 vertices from X.
If the convex hull of X is a closed set (as happens, for instance, if X is a finite set or more generally a compact set), then it is the intersection of all closed halfspaces containing X. The hyperplane separation theorem proves that in this case, each point not in the convex hull can be separated from the convex hull by a halfspace. However, there exist convex sets, and convex hulls of sets, that cannot be represented in this way. One example is an open halfspace together with a single point on its boundary.
More abstractly, the convexhull operator Conv() has the characteristic properties of a closure operator:

It is extensive, meaning that the convex hull of every set X is a superset of X.

It is nondecreasing, meaning that, for every two sets X and Y with X ⊆ Y, the convex hull of X is a subset of the convex hull of Y.

It is idempotent, meaning that for every X, the convex hull of the convex hull of X is the same as the convex hull of X.
Convex hull of a finite point set
Convex hull of some points in the plane
The convex hull of a finite point set S is the set of all convex combinations of its points. In a convex combination, each point x_i in S is assigned a weight or coefficient \alpha_i in such a way that the coefficients are all nonnegative and sum to one, and these weights are used to compute a weighted average of the points. For each choice of coefficients, the resulting convex combination is a point in the convex hull, and the whole convex hull can be formed by choosing coefficients in all possible ways. Expressing this as a single formula, the convex hull is the set:

\left\{\sum_{i=1}^{S} \alpha_i x_i \mathrel{\Bigg} (\forall i: \alpha_i\ge 0)\wedge \sum_{i=1}^{S} \alpha_i=1 \right\}.
The convex hull of a finite point set S \in \mathbb{R}^n forms a convex polygon when n = 2, or more generally a convex polytope in \mathbb{R}^n. Each point x_i in S that is not in the convex hull of the other points (that is, such that x_i\notin\operatorname{Conv}(S\setminus\{x_i\})) is called a vertex of \operatorname{Conv}(S). In fact, every convex polytope in \mathbb{R}^n is the convex hull of its vertices.
Convex hull of a finite set: elasticband analogy
If the points of S are all on a line, the convex hull is the line segment joining the outermost two points. When the set S is a nonempty finite subset of the plane (that is, twodimensional), we may imagine stretching a rubber band so that it surrounds the entire set S and then releasing it, allowing it to contract; when it becomes taut, it encloses the convex hull of S.^{[1]}
In two dimensions, the convex hull is sometimes partitioned into two polygonal chains, the upper hull and the lower hull, stretching between the leftmost and rightmost points of the hull. More generally, for points in any dimension in general position, each facet of the convex hull is either oriented upwards (separating the hull from points directly above it) or downwards; the union of the upwardfacing facets forms a topological disk, the upper hull, and similarly the union of the downwardfacing facets forms the lower hull.^{[3]}
Computation of convex hulls
In computational geometry, a number of algorithms are known for computing the convex hull for a finite set of points and for other geometric objects.
Computing the convex hull means constructing an unambiguous, efficient representation of the required convex shape. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and h, the number of points on the convex hull.
For points in two and three dimensions, outputsensitive algorithms are known that compute the convex hull in time O(n log h). For dimensions d higher than 3, the time for computing the convex hull is O(n^{\lfloor d/2\rfloor}), matching the worstcase output complexity of the problem.
Minkowski addition and convex hulls
Minkowski addition of sets. The
sum of the squares Q
_{1}=[0,1]
^{2} and Q
_{2}=[1,2]
^{2} is the square Q
_{1}+Q
_{2}=[1,3]
^{2}.
Three squares are shown in the nonnegative quadrant of the Cartesian plane. The square Q_{1}=[0,1]×[0,1] is green. The square Q_{2}=[1,2]×[1,2] is brown, and it sits inside the turquoise square Q_{1}+Q_{2}=[1,3]×[1,3].
The operation of taking convex hulls behaves well with respect to the Minkowski addition of sets.

In a real vectorspace, the Minkowski sum of two (nonempty) sets S_{1} and S_{2} is defined to be the set S_{1} + S_{2} formed by the addition of vectors elementwise from the summandsets

S_{1} + S_{2} = { x_{1} + x_{2} : x_{1} ∈ S_{1} and x_{2} ∈ S_{2} }.
More generally, the Minkowski sum of a finite family of (nonempty) sets S_{n} is the set formed by elementwise addition of vectors

∑ S_{n} = { ∑ x_{n} : x_{n} ∈ S_{n} }.

For all subsets S_{1} and S_{2} of a real vectorspace, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls

Conv( S_{1} + S_{2} ) = Conv( S_{1} ) + Conv( S_{2} ).
This result holds more generally for each finite collection of nonempty sets

Conv( ∑ S_{n} ) = ∑ Conv( S_{n} ).
In other words, the operations of Minkowski summation and of forming convex hulls are commuting operations.^{[5]}^{[6]}
These results show that Minkowski addition differs from the union operation of set theory; indeed, the union of two convex sets need not be convex: The inclusion Conv(S) ∪ Conv(T) ⊆ Conv(S ∪ T) is generally strict. The convexhull operation is needed for the set of convex sets to form a lattice, in which the "join" operation is the convex hull of the union of two convex sets

Conv(S)∨Conv(T) = Conv( S ∪ T ) = Conv( Conv(S) ∪ Conv(T) ).
Relations to other structures
The Delaunay triangulation of a point set and its dual, the Voronoi diagram, are mathematically related to convex hulls: the Delaunay triangulation of a point set in R^{n} can be viewed as the projection of a convex hull in R^{n+1}.
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.^{[8]} For instance, the closed set

\left\{(x,y)\mid y\ge \frac{1}{1+x^2}\right\}
has the open upper halfplane as its convex hull.
Applications
The problem of finding convex hulls finds its practical applications in pattern recognition, image processing, statistics, geographic information system, game theory, construction of phase diagrams, and static code analysis by abstract interpretation. It also serves as a tool, a building block for a number of other computationalgeometric algorithms such as the rotating calipers method for computing the width and diameter of a point set.
See also
Notes

^ ^{a} ^{b} de Berg et al. (2000), p. 3.

^ de Berg et al. (2000), p. 6. The idea of partitioning the hull into two chains comes from an efficient variant of Graham scan by Andrew (1979).

^ Krein & Šmulian (1940), Theorem 3, pages 562–563.

^ For the commutativity of Minkowski addition and convexification, see Theorem 1.1.2 (pages 2–3) in Schneider (1993); this reference discusses much of the literature on the convex hulls of Minkowski sumsets in its "Chapter 3 Minkowski addition" (pages 126–196).

^ Grünbaum (2003), p. 16.
References

Andrew, A. M. (1979), "Another efficient algorithm for convex hulls in two dimensions", Information Processing Letters 9 (5): 216–219, .

Brown, K. Q. (1979), "Voronoi diagrams from convex hulls", Information Processing Letters 9 (5): 223–228, .

.

.

.

.

.

Schneider, Rolf (1993), Convex bodies: The Brunn–Minkowski theory, Encyclopedia of Mathematics and its Applications 44, Cambridge: Cambridge University Press, .
External links
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.