In
mathematicsMathematics 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
realIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
vector spaceA 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 setIn 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 combinationIn 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 geometryComputational 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
planeIn 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 operatorIn 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 |
| idempotent Idempotence 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 combinationIn 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
subsetIn 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 numberIn 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 theoremIn 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
simplicesIn 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 setIn 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 S
n 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
operationThe 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
commutingIn 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 operationIn 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 theorySet 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
inclusionIn 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
latticeIn 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" operationIn 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 polytopeA 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
vertexIn 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
lineThe 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 segmentIn 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 polygonIn 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
nonemptyIn 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
planeEuclidean 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 bandA 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
representationIn 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 triangulationIn 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 DiagramIn 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 recognitionIn 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 processingIn 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...
,
statisticsStatistics 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 analysisStatic 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 interpretationIn 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 calipersIn 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
diameterIn 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.
See also
- Hull 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
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
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
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
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
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
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 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
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...
External links
- "Convex Hull" by Eric W. Weisstein
Eric W. Weisstein is an encyclopedist who created and maintains MathWorld and Eric Weisstein's World of Science . He currently works for Wolfram Research, Inc.-Education:...
, Wolfram Demonstrations ProjectThe Wolfram Demonstrations Project is hosted by Wolfram Research, whose stated goal is to bring computational exploration to the widest possible audience. It consists of an organized, open-source collection of small interactive programs called Demonstrations, which are meant to visually and...
, 2007.