In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X.
In computational geometry, a basic problem is finding the convex hull for a given finite nonempty set of points in the plane. It is common to use the term "convex hull" for the boundary of that set, which is a convex polygon, except in the degenerate case that points are collinear. The convex hull is then typically represented by a sequence of the vertices of the line segments forming the boundary of the polygon, ordered along that boundary.
Contents
Intuitive picture
For planar objects, i.e., lying in the plane, the convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given object; when released, it will assume the shape of the required convex hull.
It may seem natural to generalise this picture to higher dimensions by imagining the objects enveloped in a sort of idealised unpressurised elastic membrane or balloon under tension. However, the equilibrium (minimumenergy) surface in this case may not be the convex hull — parts of the resulting surface may have negative curvature, like a saddle surface (see article about minimal surfaces for examples). For the case of points in 3dimensional space, if a rigid wire is first placed between each pair of points, then the balloon will spring back under tension to take the form of the convex hull of the points.
Existence of the convex hull
To show that the convex hull of a set X in a real vector space V exists, notice that X is contained in at least one convex set (the whole space V, for example), and any intersection of convex sets containing X is also a convex set containing X. It is then clear that the convex hull is the intersection of all convex sets containing X. This can be used as an alternative definition of the convex hull.
Algebraically, the convex hull of X can be characterized as the set of all of the convex combinations of finite subsets of points from X: that is, the set of points of the form , where n is an arbitrary natural number, the numbers t_{j} are nonnegative and sum to 1, and the points x_{j} are in X. It is simple to check that this set satisfies either of the two definitions above. So the convex hull H_{convex}(X) of set X is:
Full article ▸
