Convex hull

related topics
{math, number, function}
{math, energy, light}
{ship, engine, design}
{@card@, make, design}

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 (minimum-energy) 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 3-dimensional 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 \sum_{j=1}^n t_jx_j, where n is an arbitrary natural number, the numbers tj are non-negative and sum to 1, and the points xj are in X. It is simple to check that this set satisfies either of the two definitions above. So the convex hull Hconvex(X) of set X is:

Full article ▸

related documents
Bézout's theorem
List of logarithmic identities
Interior (topology)
Sigma-algebra
Deque
Inverse element
Homeomorphism
Combination
Congruence relation
Coset
Hidden Markov model
Toeplitz matrix
Infinite product
Quaternion group
CYK algorithm
Triangle inequality
Harmonic series (mathematics)
Compiler-compiler
Euclidean domain
Normal subgroup
Event (probability theory)
Monomorphism
Box-Muller transform
Identity element
Initial and terminal objects
Entailment
Torsion subgroup
Parity (mathematics)
Discrete space
Memento pattern