In mathematics, the convex hull or convex envelope of a set X of points in the Euclidean plane or in a Euclidean space is the smallest convex set that contains 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 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 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 minimal convex set containing X The intersection of all convex sets containing X The set of all combinations of points in X. The union of all simplices with vertices in X and it is not obvious that the first definition makes sense, why should there exist a unique minimal convex set containing X, for every X. Thus, it is exactly the unique minimal convex set containing X. Each convex set containing X must contain all convex combinations of points in X, in fact, according to Carathéodorys 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. If the convex hull of X is a set, then it is the intersection of all closed half-spaces containing X. The hyperplane separation theorem proves that in 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, more abstractly, the convex-hull 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 non-decreasing, meaning that, for 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 hull of the convex hull of X is the same as the convex hull of X. The convex hull of a point set S is the set of all convex combinations of its points. For each choice of coefficients, the convex combination is a point in the convex hull. Expressing this as a formula, the convex hull is the set. The convex hull of a point set S ⊊ R n forms a convex polygon when n =2. Each point x i in S that is not in the hull of the other points is called a vertex of Conv . In fact, every convex polytope in R n is the hull of its vertices
Convex hull of some points in the plane
The convex hull of the red set is the blue and red convex set.