Convex hull

In mathematics, the convex hull or convex envelope or convex closure of a set X of points in the Euclidean plane or in a Euclidean space (or, more generally, in an affine space over the reals) 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 enclosed by a rubber band stretched around X. In mathematics, the convex hull or convex envelope or convex closure of a set X of points in the Euclidean plane or in a Euclidean space (or, more generally, in an affine space over the reals) 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 enclosed by a rubber band stretched around X. Formally, the convex hull may be defined either 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 low-dimensional Euclidean spaces is one of the fundamental problems of computational geometry. 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 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 well-defined, 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 N-dimensional 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 N-dimensional 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 half-spaces 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 half-space. However, there exist convex sets, and convex hulls of sets, that cannot be represented in this way. Open halfspaces are such examples. More abstractly, the convex-hull operator Conv() has the characteristic properties of a closure operator: The convex hull of a finite point set S {displaystyle S} is the set of all convex combinations of its points. In a convex combination, each point x i {displaystyle x_{i}} in S {displaystyle S} is assigned a weight or coefficient α i {displaystyle alpha _{i}} in such a way that the coefficients are all non-negative 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: The convex hull of a finite point set S ⊊ R n {displaystyle Ssubsetneq mathbb {R} ^{n}} forms a convex polygon when n = 2, or more generally a convex polytope in R n {displaystyle mathbb {R} ^{n}} . Each point x i {displaystyle x_{i}} in S {displaystyle S} that is not in the convex hull of the other points (that is, such that x i ∉ Conv ⁡ ( S ∖ { x i } ) {displaystyle x_{i} otin operatorname {Conv} (Ssetminus {x_{i}})} ) is called a vertex of Conv ⁡ ( S ) {displaystyle operatorname {Conv} (S)} . In fact, every convex polytope in R n {displaystyle mathbb {R} ^{n}} is the convex hull of its vertices.