Convex hull

# Convex hull

Overview

Discussion
 Ask a question about 'Convex hull' Start a new discussion about 'Convex hull' Answer questions from other users Full Discussion Forum

Recent Discussions
Encyclopedia

In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the convex hull or convex envelope for a set of points X in a real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

V is the minimal convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...

containing X.

The convex hull also has a linear-algebraic characterization: the convex hull of X is the set of all convex combination
Convex combination
In convex geometry, a convex combination is a linear combination of points where all coefficients are non-negative and sum up to 1....

s of points in X.

In computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

, a basic problem is finding the convex hull for a given finite set of points in the plane
Plane (mathematics)
In mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...

.

## 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.

The convex-hull operator Conv has the characteristic properties of a hull operator
Closure operator
In mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....

:
 extensive S ⊆ Conv(S), non-decreasing S ⊆ T implies that Conv(S) ⊆ Conv(T), and idempotentIdempotenceIdempotence is the property of certain operations in mathematics and computer science, that they can be applied multiple times without changing the result beyond the initial application... Conv(Conv(S)) = Conv(S).

Thus, the convex-hull operator is a proper "hull" operator.

## Algebraic characterization

Algebraically, the convex hull of X can be characterized as the set of all of the convex combination
Convex combination
In convex geometry, a convex combination is a linear combination of points where all coefficients are non-negative and sum up to 1....

s of finite subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of points from X: that is, the set of points of the form , where n is an arbitrary natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

, the numbers are non-negative and sum to 1, and the points are in X. It is simple to check that this set satisfies either of the two definitions above.
So the convex hull of set X is:

In fact, according to Carathéodory's theorem
Carathéodory's theorem (convex hull)
In convex geometry Carathéodory's theorem states that if a point x of Rd lies in the convex hull of a set P, there is a subset P′ of P consisting of d+1 or fewer points such that x lies in the convex hull of P′. Equivalently, x lies in an r-simplex with vertices in P, where r \leq d...

, 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. This is equivalent to saying that the convex hull of X is the union of all simplices
Simplex
In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron,...

with at most N+1 vertices from X.

The convex hull is defined for any kind of objects made up of points in a vector space, which may have any number of dimensions, including infinite-dimensional vector spaces. The convex hull of finite sets of points and other geometrical objects in a two-dimensional plane or three-dimensional space are special cases of practical importance.

### Minkowski addition and convex hulls

The operation of taking convex hulls behaves well with respect to the Minkowski addition of sets.
• In a real vector-space, the Minkowski sum
In geometry, the Minkowski sum of two sets A and B in Euclidean space is the result of adding every element of A to every element of B, i.e...

of two (non-empty) sets S1 and S2 is defined to be the set
Sumset
In additive combinatorics, the sumset of two subsets A and B of an abelian group G is defined to be the set of all sums of an element from A with an element from B...

S1 + S2 formed by the addition of vectors element-wise from the summand-sets
S1 + S2 = { x1 + x2 : x1 ∈ S1 and x2 ∈ S2 }.

More generally, the Minkowski sum of a finite family of (non-empty) sets Sn is the set formed by element-wise addition of vectors
∑ Sn = { ∑ xn : xn ∈ Sn }.

• For all subsets S1 and S2 of a real vector-space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls
Conv( S1 + S2 ) = Conv( S1 ) + Conv( S2 ).

This result holds more generally for each finite collection of non-empty sets
Conv(  ∑ Sn  ) = ∑ Conv( Sn ).

In other words, the operation
Operation (mathematics)
The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....

s of Minkowski summation and of forming convex hulls are commuting
Commutativity
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...

operations.

These results show that Minkowski addition differs from the union operation
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...

of set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

; indeed, the union of two convex sets need not be convex: The inclusion
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

Conv(S) ∪ Conv(T) ⊆ Conv(S ∪ T) is generally strict. The convex-hull operation is needed for the set of convex sets to form a lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...

, in which the "join" operation
Join and meet
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...

is the convex hull of the union of two convex sets
Conv(S)∨Conv(T) = Conv( S ∪ T ) = Conv( Conv(S) ∪ Conv(T) ).

## Convex hull of a finite point set

The convex hull of a finite point set forms a convex polytope
Convex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn...

in . Each such that Conv(P \ {p}) is called a vertex
Vertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...

of Conv(P). In fact, a convex polytope in is the convex hull of its vertices.

If the points are all on a line
Line (geometry)
The notion of line or straight line was introduced by the ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects...

, the convex hull is the line segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...

joining the outermost two points. In the planar case, the convex hull is a convex polygon
Convex polygon
In geometry, a polygon can be either convex or concave .- Convex polygons :A convex polygon is a simple polygon whose interior is a convex set...

unless all points are on the same line. Similarly, in three dimensions the convex hull is in general the minimal convex polyhedron that contains all the points in the set.
When the set X is a nonempty
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

finite subset of the plane
Euclidean geometry
Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...

(that is, two-dimensional), we may imagine stretching a rubber band
Rubber band
A rubber band is a short length of rubber and latex formed in the shape of a loop and is commonly used to hold multiple objects together...

so that it surrounds the entire set X and then releasing it, allowing it to contract; when it becomes taut, it encloses the convex hull of X.

## 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
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...

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.

## Relations to other geometric structures

The Delaunay triangulation
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...

of a point set and its dual, the Voronoi Diagram
Voronoi diagram
In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...

, are mathematically related to convex hulls: the Delaunay triangulation of a point set in Rn can be viewed as the projection of a convex hull in Rn+1.

## Applications

The problem of finding convex hulls finds its practical applications in pattern recognition
Pattern recognition
In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...

, image processing
Image processing
In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...

, statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....

, GIS and static code analysis
Static code analysis
Static program analysis is the analysis of computer software that is performed without actually executing programs built from that software In most cases the analysis is performed on some version of the source code and in the other cases some form of the object code...

by abstract interpretation
Abstract interpretation
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer program which gains information about its semantics In...

. It also serves as a tool, a building block for a number of other computational-geometric algorithms such as the rotating calipers
Rotating calipers
In computational geometry, rotating calipers is a method used to construct efficient algorithms for a number of problems.The method was first used by Michael Shamos in 1978 for determining all antipodal pairs of points and vertices on a convex polygon....

method for computing the width and diameter
Diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints are on the circle. The diameters are the longest chords of the circle...

of a point set.

• Hull operator
Closure operator
In mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....

• Affine hull
Affine hull
In mathematics, the affine hull of a set S in Euclidean space Rn is the smallest affine set containing S, or equivalently, the intersection of all affine sets containing S...

• Linear hull
• Krein–Milman theorem
• Choquet theory
Choquet theory
In mathematics, Choquet theory is an area of functional analysis and convex analysis created by Gustave Choquet. It is concerned with measures with support on the extreme points of a convex set C...

• Holomorphically convex hull
Holomorphically convex hull
In mathematics, more precisely in complex analysis, the holomorphically convex hull of a given compact set in the n-dimensional complex space Cn is defined as follows....

• Orthogonal convex hull
Orthogonal convex hull
In Euclidean geometry, a set K\subset\R^n is defined to be orthogonally convex if, for every line L that is parallel to one of the axes of the Cartesian coordinate system, the intersection of K with L is empty, a point, or a single interval...

• Oloid
Oloid
An oloid is a geometric object that was discovered by Paul Schatz in 1929. It is formed by taking the convex hull of the shape made by intersecting two disks of equal radius at right angles within one another, with the distance between the centers of the disks equal to their radius...

• Carathéodory's theorem
Carathéodory's theorem (convex hull)
In convex geometry Carathéodory's theorem states that if a point x of Rd lies in the convex hull of a set P, there is a subset P′ of P consisting of d+1 or fewer points such that x lies in the convex hull of P′. Equivalently, x lies in an r-simplex with vertices in P, where r \leq d...

• Helly's theorem
Helly's theorem
Helly's theorem is a basic result in discrete geometry describing the ways that convex sets may intersect each other. It was discovered by Eduard Helly in 1913, but not published by him until 1923, by which time alternative proofs by and had already appeared...

• Shapley–Folkman lemma
Shapley–Folkman lemma
In geometry and economics, the Shapley–Folkman lemma describes the Minkowski addition of sets in a vector space. Minkowski addition is defined as the addition of the sets' members: for example, adding the set consisting of the integers zero and one to itself yields the set consisting of...