Minimum Convex Polygon
   HOME

TheInfoList



OR:

In
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, the convex hull or convex envelope or convex closure of a shape is the smallest
convex set In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex r ...
that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
, or equivalently as the set of all
convex combination In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other word ...
s of points in the subset. For a
bounded Boundedness or bounded may refer to: Economics * Bounded rationality, the idea that human rationality in decision-making is bounded by the available information, the cognitive limitations, and the time available to make the decision * Bounded e ...
subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset. Convex hulls of
open set In mathematics, open sets are a generalization of open intervals in the real line. In a metric space (a set along with a distance defined between any two points), open sets are the sets that, with every point , contain all points that are suf ...
s are open, and convex hulls of
compact set In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
s are compact. Every compact convex set is the convex hull of its
extreme point In mathematics, an extreme point of a convex set S in a real or complex vector space is a point in S which does not lie in any open line segment joining two points of S. In linear programming problems, an extreme point is also called vertex or ...
s. The convex hull operator is an example of a
closure operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S : Closure operators are dete ...
, and every
antimatroid In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids ...
can be represented by applying this closure operator to finite sets of points. The
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
ic problems of finding the convex hull of a finite set of points in the plane or other low-dimensional Euclidean spaces, and its
dual Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual (grammatical ...
problem of intersecting half-spaces, are fundamental problems of
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 ar ...
. They can be solved in time O(n\log n) for two or three dimensional point sets, and in time matching the worst-case output complexity given by the
upper bound theorem In mathematics, the upper bound theorem states that cyclic polytopes have the largest possible number of faces among all convex polytopes with a given dimension and number of vertices. It is one of the central results of polyhedral combinatorics. ...
in higher dimensions. As well as for finite point sets, convex hulls have also been studied for
simple polygon In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise ...
s,
Brownian motion Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas). This pattern of motion typically consists of random fluctuations in a particle's position insi ...
,
space curve In mathematics, a curve (also called a curved line in older texts) is an object similar to a line, but that does not have to be straight. Intuitively, a curve may be thought of as the trace left by a moving point. This is the definition that a ...
s, and epigraphs of functions. Convex hulls have wide applications in mathematics, statistics, combinatorial optimization, economics, geometric modeling, and ethology. Related structures include the
orthogonal convex hull In geometry, a set is defined to be orthogonally convex if, for every line that is parallel to one of standard basis vectors, the intersection of with is empty, a point, or a single segment. The term "orthogonal" refers to corresponding C ...
,
convex layers In computational geometry, the convex layers of a set of points in the Euclidean plane are a sequence of nested convex polygons having the points as their vertices. The outermost one is the convex hull of the points and the rest are formed in the s ...
,
Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...
and
Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed th ...
, and
convex skull In computational geometry, the potato peeling or convex skull problem is a problem of finding the convex polygon of the largest possible area that lies within a given non-convex polygon. It was posed independently by Goodman and Woo, and solved in ...
.


Definitions

A set of points in a
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
is defined to be
convex Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytope ...
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 (unique) minimal convex set containing X #The intersection of all convex sets containing X #The set of all
convex combination In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other word ...
s of points in X #The union of all
simplices In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
with vertices in X For
bounded set :''"Bounded" and "boundary" are distinct concepts; for the latter see boundary (topology). A circle in isolation is a boundaryless bounded set, while the half plane is unbounded yet has a boundary. In mathematical analysis and related areas of mat ...
s in the Euclidean plane, not all on one line, the boundary of the convex hull is the
simple closed curve In topology, the Jordan curve theorem asserts that every ''Jordan curve'' (a plane simple closed curve) divides the plane into an " interior" region bounded by the curve and an "exterior" region containing all of the nearby and far away exterior ...
with minimum
perimeter A perimeter is a closed path that encompasses, surrounds, or outlines either a two dimensional shape or a one-dimensional length. The perimeter of a circle or an ellipse is called its circumference. Calculating the perimeter has several pract ...
containing X. One may imagine stretching a
rubber band A rubber band (also known as an elastic band, gum band or lacky band) is a loop of rubber, usually ring or oval shaped, and commonly used to hold multiple objects together. The rubber band was patented in England on March 17, 1845 by Stephen P ...
so that it surrounds the entire set S and then releasing it, allowing it to contract; when it becomes taut, it encloses the convex hull of S. This formulation does not immediately generalize to higher dimensions: for a finite set of points in three-dimensional space, a neighborhood of a
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
of the points encloses them with arbitrarily small surface area, smaller than the surface area of the convex hull. However, in higher dimensions, variants of the
obstacle problem The obstacle problem is a classic motivating example in the mathematical study of variational inequalities and free boundary problems. The problem is to find the equilibrium position of an elastic membrane whose boundary is held fixed, and which ...
of finding a minimum-energy surface above a given shape can have the convex hull as their solution. For objects in three dimensions, the first definition states that the convex hull is the smallest possible convex
bounding volume In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operatio ...
of the objects. The definition using intersections of convex sets may be extended to
non-Euclidean geometry In mathematics, non-Euclidean geometry consists of two geometries based on axioms closely related to those that specify Euclidean geometry. As Euclidean geometry lies at the intersection of metric geometry and affine geometry, non-Euclidean geo ...
, and the definition using convex combinations may be extended from Euclidean spaces to arbitrary
real vector space Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...
s or
affine space In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties relate ...
s; convex hulls may also be generalized in a more abstract way, to
oriented matroid An oriented matroid is a mathematics, mathematical mathematical structure, structure that abstracts the properties of directed graphs, Vector space, vector arrangements over ordered fields, and Arrangement of hyperplanes, hyperplane arrangements o ...
s.


Equivalence of definitions

It is not obvious that the first definition makes sense: why should there exist a unique minimal convex set containing X, for every X? However, the second definition, the intersection of all convex sets containing X, is well-defined. It is a subset of every other convex set Y that contains X, because Y is included among the sets being intersected. Thus, it is exactly the unique minimal convex set containing X. Therefore, the first two definitions are equivalent. Each convex set containing X must (by the assumption that it is convex) contain all convex combinations of points in X, so the set of all convex combinations is contained in the intersection of all convex sets containing X. Conversely, the set of all convex combinations is itself a convex set containing X, so it also contains the intersection of all convex sets containing X, and therefore the second and third definitions are equivalent., p. 12; , p. 17. In fact, according to Carathéodory's theorem, if X is a subset of a d-dimensional Euclidean space, every convex combination of finitely many points from X is also a convex combination of at most d+1 points in X. The set of convex combinations of a (d+1)-tuple of points is a
simplex In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
; in the plane it is a
triangle A triangle is a polygon with three Edge (geometry), edges and three Vertex (geometry), vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC. In Euclidean geometry, an ...
and in three-dimensional space it is a tetrahedron. Therefore, every convex combination of points of X belongs to a simplex whose vertices belong to X, and the third and fourth definitions are equivalent.


Upper and lower hulls

In two dimensions, the convex hull is sometimes partitioned into two parts, the upper hull and the lower hull, stretching between the leftmost and rightmost points of the hull. More generally, for convex hulls in any dimension, one can partition the boundary of the hull into upward-facing points (points for which an upward ray is disjoint from the hull), downward-facing points, and extreme points. For three-dimensional hulls, the upward-facing and downward-facing parts of the boundary form topological disks.


Topological properties


Closed and open hulls

The ''closed convex hull'' of a set is the closure of the convex hull, and the ''open convex hull'' is the
interior Interior may refer to: Arts and media * ''Interior'' (Degas) (also known as ''The Rape''), painting by Edgar Degas * ''Interior'' (play), 1895 play by Belgian playwright Maurice Maeterlinck * ''The Interior'' (novel), by Lisa See * Interior de ...
(or in some sources the
relative interior In mathematics, the relative interior of a set is a refinement of the concept of the interior, which is often more useful when dealing with low-dimensional sets placed in higher-dimensional spaces. Formally, the relative interior of a set S (de ...
) of the convex hull. The closed convex hull of X is the intersection of all closed half-spaces containing X. If the convex hull of X is already a
closed set In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric space, a cl ...
itself (as happens, for instance, if X is a
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. Th ...
or more generally a
compact set In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
), then it equals the closed convex hull. However, an intersection of closed half-spaces is itself closed, so when a convex hull is not closed it cannot be represented in this way. If the open convex hull of a set X is d-dimensional, then every point of the hull belongs to an open convex hull of at most 2d points of X. The sets of vertices of a square, regular octahedron, or higher-dimensional
cross-polytope In geometry, a cross-polytope, hyperoctahedron, orthoplex, or cocube is a regular, convex polytope that exists in ''n''- dimensional Euclidean space. A 2-dimensional cross-polytope is a square, a 3-dimensional cross-polytope is a regular octahed ...
provide examples where exactly 2d points are needed.


Preservation of topological properties

Topologically, the convex hull of an
open set In mathematics, open sets are a generalization of open intervals in the real line. In a metric space (a set along with a distance defined between any two points), open sets are the sets that, with every point , contain all points that are suf ...
is always itself open, and the convex hull of a compact set is always itself compact. However, there exist closed sets for which the convex hull is not closed. For instance, the closed set :\left \ (the set of points that lie on or above the
witch of Agnesi In mathematics, the witch of Agnesi () is a cubic plane curve defined from two diametrically opposite points of a circle. It gets its name from Italian mathematician Maria Gaetana Agnesi, and from a mistranslation of an Italian word for a sail ...
) has the open
upper half-plane In mathematics, the upper half-plane, \,\mathcal\,, is the set of points in the Cartesian plane with > 0. Complex plane Mathematicians sometimes identify the Cartesian plane with the complex plane, and then the upper half-plane corresponds to t ...
as its convex hull. The compactness of convex hulls of compact sets, in finite-dimensional Euclidean spaces, is generalized by the Krein–Smulian theorem, according to which the closed convex hull of a weakly compact subset of a
Banach space In mathematics, more specifically in functional analysis, a Banach space (pronounced ) is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vector ...
(a subset that is compact under the
weak topology In mathematics, weak topology is an alternative term for certain initial topologies, often on topological vector spaces or spaces of linear operators, for instance on a Hilbert space. The term is most commonly used for the initial topology of a ...
) is weakly compact.


Extreme points

An
extreme point In mathematics, an extreme point of a convex set S in a real or complex vector space is a point in S which does not lie in any open line segment joining two points of S. In linear programming problems, an extreme point is also called vertex or ...
of a convex set is a point in the set that does not lie on any open line segment between any other two points of the same set. For a convex hull, every extreme point must be part of the given set, because otherwise it cannot be formed as a convex combination of given points. According to the
Krein–Milman theorem In the mathematical theory of functional analysis, the Krein–Milman theorem is a proposition about compact convex sets in locally convex topological vector spaces (TVSs). This theorem generalizes to infinite-dimensional spaces and to arbitrar ...
, every compact convex set in a Euclidean space (or more generally in a
locally convex topological vector space In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological vec ...
) is the convex hull of its extreme points. However, this may not be true for convex sets that are not compact; for instance, the whole Euclidean plane and the open unit ball are both convex, but neither one has any extreme points.
Choquet theory In mathematics, Choquet theory, named after Gustave Choquet, is an area of functional analysis and convex analysis concerned with measures which have support on the extreme points of a convex set ''C''. Roughly speaking, every vector of ''C'' should ...
extends this theory from finite convex combinations of extreme points to infinite combinations (integrals) in more general spaces.


Geometric and algebraic properties


Closure operator

The convex-hull operator has the characteristic properties of a
closure operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S : Closure operators are dete ...
: *It is ''extensive'', meaning that the convex hull of every set X is a superset of X. *It is '' non-decreasing'', meaning that, for every two sets X and Y with X\subseteq Y, the convex hull of X is a subset of the convex hull of Y. *It is ''
idempotent Idempotence (, ) is the property of certain operation (mathematics), operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence ...
'', meaning that for every X, the convex hull of the convex hull of X is the same as the convex hull of X. When applied to a finite set of points, this is the closure operator of an
antimatroid In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids ...
, the shelling antimatroid of the point set. Every antimatroid can be represented in this way by convex hulls of points in a Euclidean space of high-enough dimension.


Minkowski sum

The operations of constructing the convex hull and taking the
Minkowski sum In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors ''A'' and ''B'' in Euclidean space is formed by adding each vector in ''A'' to each vector in ''B'', i.e., the set : A + B = \. Analogously, the Minkowski ...
commute with each other, in the sense that the Minkowski sum of convex hulls of sets gives the same result as the convex hull of the Minkowski sum of the same sets. This provides a step towards the Shapley–Folkman theorem bounding the distance of a Minkowski sum from its convex hull.


Projective duality

The
projective dual In geometry, a striking feature of projective planes is the symmetry of the roles played by points and lines in the definitions and theorems, and (plane) duality is the formalization of this concept. There are two approaches to the subject of du ...
operation to constructing the convex hull of a set of points is constructing the intersection of a family of closed halfspaces that all contain the origin (or any other designated point).


Special cases


Finite point sets

The convex hull of a finite point set S \subset \R^d forms a
convex polygon In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...
when d=2, or more generally a
convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
in \R^d. Each extreme point of the hull is called a
vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...
, and (by the Krein–Milman theorem) every convex polytope is the convex hull of its vertices. It is the unique convex polytope whose vertices belong to S and that encloses all of S. For sets of points in
general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that ar ...
, the convex hull is a
simplicial polytope In geometry, a simplicial polytope is a polytope whose facets are all simplices. For example, a ''simplicial polyhedron'' in three dimensions contains only triangular facesPolyhedra, Peter R. Cromwell, 1997. (p.341) and corresponds via Steinitz's ...
. According to the
upper bound theorem In mathematics, the upper bound theorem states that cyclic polytopes have the largest possible number of faces among all convex polytopes with a given dimension and number of vertices. It is one of the central results of polyhedral combinatorics. ...
, the number of faces of the convex hull of n points in d-dimensional Euclidean space is O(n^). In particular, in two and three dimensions the number of faces is at most linear in n.


Simple polygons

The convex hull of a
simple polygon In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise ...
encloses the given polygon and is partitioned by it into regions, one of which is the polygon itself. The other regions, bounded by a
polygonal chain In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points (A_1, A_2, \dots, A_n) called its vertices. The curve itself consists of the line segments co ...
of the polygon and a single convex hull edge, are called ''pockets''. Computing the same decomposition recursively for each pocket forms a hierarchical description of a given polygon called its ''convex differences tree''. Reflecting a pocket across its convex hull edge expands the given simple polygon into a polygon with the same perimeter and larger area, and the
Erdős–Nagy theorem The Erdős–Nagy theorem is a result in discrete geometry stating that a non-convex simple polygon can be made into a convex polygon by a finite sequence of flips. The flips are defined by taking a convex hull of a polygon and reflecting a pock ...
states that this expansion process eventually terminates.


Brownian motion

The curve generated by
Brownian motion Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas). This pattern of motion typically consists of random fluctuations in a particle's position insi ...
in the plane, at any fixed time, has probability 1 of having a convex hull whose boundary forms a continuously differentiable curve. However, for any angle \theta in the range \pi/2<\theta<\pi, there will be times during the Brownian motion where the moving particle touches the boundary of the convex hull at a point of angle \theta. The
Hausdorff dimension In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was first introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of a ...
of this set of exceptional times is (with high probability) 1-\pi/2\theta.


Space curves

For the convex hull of a
space curve In mathematics, a curve (also called a curved line in older texts) is an object similar to a line, but that does not have to be straight. Intuitively, a curve may be thought of as the trace left by a moving point. This is the definition that a ...
or finite set of space curves in general position in three-dimensional space, the parts of the boundary away from the curves are developable and
ruled surface In geometry, a surface is ruled (also called a scroll) if through every point of there is a straight line that lies on . Examples include the plane, the lateral surface of a cylinder or cone, a conical surface with elliptical directrix, the ...
s. Examples include the
oloid An oloid is a three-dimensional curved geometric object that was discovered by Paul Schatz in 1929. It is the convex hull of a skeletal frame made by placing two linked congruent circles in perpendicular planes, so that the center of each circl ...
, the convex hull of two circles in perpendicular planes, each passing through the other's center, the
sphericon In solid geometry, the sphericon is a solid that has a continuous developable surface with two congruent, semi-circular edges, and four vertices that define a square. It is a member of a special family of rollers that, while being rolled on ...
, the convex hull of two semicircles in perpendicular planes with a common center, and D-forms, the convex shapes obtained from
Alexandrov's uniqueness theorem The Alexandrov uniqueness theorem is a rigidity theorem in mathematics, describing three-dimensional convex polyhedra in terms of the distances between points on their surfaces. It implies that convex polyhedra with distinct shapes from each othe ...
for a surface formed by gluing together two planar convex sets of equal perimeter.


Functions

The convex hull or
lower convex envelope In mathematics, the lower convex envelope \breve f of a function f defined on an interval ,b/math> is defined at each point of the interval as the supremum of all convex functions that lie under that function, i.e. : \breve f (x) = \sup\. See ...
of a function f on a real vector space is the function whose epigraph is the lower convex hull of the epigraph of f. It is the unique maximal
convex function In mathematics, a real-valued function is called convex if the line segment between any two points on the graph of a function, graph of the function lies above the graph between the two points. Equivalently, a function is convex if its epigra ...
majorized by f. The definition can be extended to the convex hull of a set of functions (obtained from the convex hull of the union of their epigraphs, or equivalently from their
pointwise minimum In mathematics, the lower envelope or pointwise minimum of a finite set of functions is the pointwise minimum of the functions, the function whose value at every point is the minimum of the values of the functions in the given set. The concept of ...
) and, in this form, is dual to the
convex conjugate In mathematics and mathematical optimization, the convex conjugate of a function is a generalization of the Legendre transformation which applies to non-convex functions. It is also known as Legendre–Fenchel transformation, Fenchel transformation ...
operation.


Computation

In
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 ar ...
, 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 Representation may refer to: Law and politics *Representation (politics), political activities undertaken by elected representatives, as well as other theories ** Representative democracy, type of democracy in which elected officials represent a ...
of the required convex shape. Output representations that have been considered for convex hulls of point sets include a list of
linear inequalities Linearity is the property of a mathematical relationship (''function (mathematics), function'') that can be graph of a function, graphically represented as a straight Line (geometry), line. Linearity is closely related to ''Proportionality (mat ...
describing the
facets A facet is a flat surface of a geometric shape, e.g., of a cut gemstone. Facet may also refer to: Arts, entertainment, and media * ''Facets'' (album), an album by Jim Croce * ''Facets'', a 1980 album by jazz pianist Monty Alexander and his tri ...
of the hull, an
undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
of facets and their adjacencies, or the full
face lattice A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
of the hull. In two dimensions, it may suffice more simply to list the points that are vertices, in their cyclic order around the hull. For convex hulls in two or three dimensions, 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, which may be significantly smaller than n. For higher-dimensional hulls, the number of faces of other dimensions may also come into the analysis.
Graham scan Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(''n'' log ''n''). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices o ...
can compute the convex hull of n points in the plane in time O(n\log n). For points in two and three dimensions, more complicated
output-sensitive algorithm In computer science, an output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of, or in addition to, the size of the input. For certain problems where the output size varies widely, for example fro ...
s are known that compute the convex hull in time O(n\log h). These include
Chan's algorithm In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set P of n points, in 2- or 3-dimensional space. The algorithm takes O(n \log h) time, where h is t ...
and the
Kirkpatrick–Seidel algorithm The Kirkpatrick–Seidel algorithm, proposed by its authors as a potential "ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with \mathcal(n \log h) time complexity, where n is th ...
. For dimensions d>3, the time for computing the convex hull is O(n^), matching the worst-case output complexity of the problem. The convex hull of a simple polygon in the plane can be constructed in
linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.
Dynamic convex hull The dynamic convex hull problem is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for input data undergoing a sequence of discrete changes, i.e., when input da ...
data structures can be used to keep track of the convex hull of a set of points undergoing insertions and deletions of points, and
kinetic convex hull A kinetic convex hull data structure is a kinetic data structure that maintains the convex hull of a set of continuously moving points. It should be distinguished from dynamic convex hull data structures, which handle points undergoing discrete cha ...
structures can keep track of the convex hull for points moving continuously. The construction of convex hulls also serves as a tool, a building block for a number of other computational-geometric algorithms such as the
rotating calipers In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points. The method is so named because the idea is ana ...
method for computing the
width Length is a measure of distance. In the International System of Quantities, length is a quantity with dimension distance. In most systems of measurement a base unit for length is chosen, from which all other units are derived. In the Interna ...
and
diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...
of a point set.


Related structures

Several other shapes can be defined from a set of points in a similar way to the convex hull, as the minimal superset with some property, the intersection of all shapes containing the points from a given family of shapes, or the union of all combinations of points for a certain type of combination. For instance: *The
affine hull In mathematics, the affine hull or affine span of a set ''S'' in Euclidean space R''n'' is the smallest affine set containing ''S'', or equivalently, the intersection of all affine sets containing ''S''. Here, an ''affine set'' may be defined ...
is the smallest affine subspace of a Euclidean space containing a given set, or the union of all affine combinations of points in the set. *The
linear hull In mathematics, the linear span (also called the linear hull or just span) of a set of vectors (from a vector space), denoted , pp. 29-30, §§ 2.5, 2.8 is defined as the set of all linear combinations of the vectors in . It can be characterize ...
is the smallest linear subspace of a vector space containing a given set, or the union of all linear combinations of points in the set. *The
conical hull Given a finite number of vectors x_1, x_2, \dots, x_n in a real vector space, a conical combination, conical sum, or weighted sum''Convex Analysis and Minimization Algorithms'' by Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal, 1993, pp. 101, 102/ ...
or positive hull of a subset of a vector space is the set of all positive combinations of points in the subset. *The
visual hull A visual hull is a geometric entity created by shape-from-silhouette 3D reconstruction technique introduced by A. Laurentini. This technique assumes the foreground object in an image can be separated from the background. Under this assumption, ...
of a three-dimensional object, with respect to a set of viewpoints, consists of the points p such that every ray from a viewpoint through p intersects the object. Equivalently it is the intersection of the (non-convex) cones generated by the outline of the object with respect to each viewpoint. It is used in
3D reconstruction In computer vision and computer graphics, 3D reconstruction is the process of capturing the shape and appearance of real objects. This process can be accomplished either by active or passive methods. If the model is allowed to change its shape i ...
as the largest shape that could have the same outlines from the given viewpoints. *The circular hull or alpha-hull of a subset of the plane is the intersection of all disks with a given radius 1/\alpha that contain the subset. *The relative convex hull of a subset of a two-dimensional
simple polygon In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise ...
is the intersection of all relatively convex supersets, where a set within the same polygon is relatively convex if it contains the
geodesic In geometry, a geodesic () is a curve representing in some sense the shortest path ( arc) between two points in a surface, or more generally in a Riemannian manifold. The term also has meaning in any differentiable manifold with a connection. ...
between any two of its points. *The
orthogonal convex hull In geometry, a set is defined to be orthogonally convex if, for every line that is parallel to one of standard basis vectors, the intersection of with is empty, a point, or a single segment. The term "orthogonal" refers to corresponding C ...
or rectilinear convex hull is the intersection of all orthogonally convex and connected supersets, where a set is orthogonally convex if it contains all axis-parallel segments between pairs of its points. *The orthogonal convex hull is a special case of a much more general construction, the hyperconvex hull, which can be thought of as the smallest
injective metric space In metric geometry, an injective metric space, or equivalently a hyperconvex metric space, is a metric space with certain properties generalizing those of the real line and of L∞ distances in higher-dimensional vector spaces. These properties can ...
containing the points of a given
metric space In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
. *The
holomorphically convex hull The theory of functions of several complex variables is the branch of mathematics dealing with complex-valued functions. The name of the field dealing with the properties of function of several complex variables is called several complex variab ...
is a generalization of similar concepts to
complex analytic manifold In differential geometry and complex geometry, a complex manifold is a manifold with an atlas of charts to the open unit disc in \mathbb^n, such that the transition maps are holomorphic. The term complex manifold is variously used to mean a com ...
s, obtained as an intersection of sublevel sets of
holomorphic functions In mathematics, a holomorphic function is a complex-valued function of one or more complex variables that is complex differentiable in a neighbourhood of each point in a domain in complex coordinate space . The existence of a complex derivati ...
containing a given set. The
Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...
of a point set and its
dual Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual (grammatical ...
, the
Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed th ...
, are mathematically related to convex hulls: the Delaunay triangulation of a point set in \R^n can be viewed as the projection of a convex hull in \R^. The
alpha shape In computational geometry, an alpha shape, or α-shape, is a family of piecewise linear simple curves in the Euclidean plane associated with the shape of a finite set of points. They were first defined by . The alpha-shape associated with a se ...
s of a finite point set give a nested family of (non-convex) geometric objects describing the shape of a point set at different levels of detail. Each of alpha shape is the union of some of the features of the Delaunay triangulation, selected by comparing their
circumradius In geometry, the circumscribed circle or circumcircle of a polygon is a circle that passes through all the vertices of the polygon. The center of this circle is called the circumcenter and its radius is called the circumradius. Not every polyg ...
to the parameter alpha. The point set itself forms one endpoint of this family of shapes, and its convex hull forms the other endpoint. The
convex layers In computational geometry, the convex layers of a set of points in the Euclidean plane are a sequence of nested convex polygons having the points as their vertices. The outermost one is the convex hull of the points and the rest are formed in the s ...
of a point set are a nested family of convex polygons, the outermost of which is the convex hull, with the inner layers constructed recursively from the points that are not vertices of the convex hull. The
convex skull In computational geometry, the potato peeling or convex skull problem is a problem of finding the convex polygon of the largest possible area that lies within a given non-convex polygon. It was posed independently by Goodman and Woo, and solved in ...
of a polygon is the largest convex polygon contained inside it. It can be found in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
, but the exponent of the algorithm is high.


Applications

Convex hulls have wide applications in many fields. Within mathematics, convex hulls are used to study
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s, matrix
eigenvalue In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
s, and
unitary element In mathematics, an element ''x'' of a *-algebra is unitary if it satisfies x^* = x^. In functional analysis, a linear operator ''A'' from a Hilbert space into itself is called unitary if it is invertible and its inverse is equal to its own adjo ...
s, and several theorems in
discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geome ...
involve convex hulls. They are used in
robust statistics Robust statistics are statistics with good performance for data drawn from a wide range of probability distributions, especially for distributions that are not normal. Robust statistical methods have been developed for many common problems, suc ...
as the outermost contour of
Tukey depth In computational geometry, the Tukey depth is a measure of the depth of a point in a fixed set of points. The concept is named after its inventor, John Tukey. Given a set of points P in ''d''-dimensional space, a point ''p'' has Tukey depth ''k' ...
, are part of the
bagplot A bagplot, or starburst plot, is a method in robust statistics for visualizing two- or three-dimensional statistical data, analogous to the one-dimensional box plot. Introduced in 1999 by Rousseuw et al., the bagplot allows one to visualize the l ...
visualization of two-dimensional data, and define risk sets of randomized decision rules. Convex hulls of
indicator vector In mathematics, the indicator vector or characteristic vector or incidence vector of a subset ''T'' of a Set (mathematics), set ''S'' is the vector x_T := (x_s)_ such that x_s = 1 if s \in T and x_s = 0 if s \notin T. If ''S'' is countable set, cou ...
s of solutions to combinatorial problems are central to
combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
and
polyhedral combinatorics Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral comb ...
. In economics, convex hulls can be used to apply methods of
convexity in economics Convexity is an important topic in economics. In the Arrow–Debreu model of general economic equilibrium, agents have convex budget sets and convex preferences: At equilibrium prices, the budget hyperplane supports the best attainable indiffer ...
to non-convex markets. In geometric modeling, the convex hull property
Bézier curve A Bézier curve ( ) is a parametric curve used in computer graphics and related fields. A set of discrete "control points" defines a smooth, continuous curve by means of a formula. Usually the curve is intended to approximate a real-world shape t ...
s helps find their crossings, and convex hulls are part of the measurement of boat hulls. And in the study of animal behavior, convex hulls are used in a standard definition of the
home range A home range is the area in which an animal lives and moves on a periodic basis. It is related to the concept of an animal's territory which is the area that is actively defended. The concept of a home range was introduced by W. H. Burt in 1943. He ...
.


Mathematics

Newton polygon In mathematics, the Newton polygon is a tool for understanding the behaviour of polynomials over local fields, or more generally, over ultrametric fields. In the original case, the local field of interest was ''essentially'' the field of formal Lau ...
s of univariate
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s and
Newton polytope In mathematics, the Newton polytope is an integral polytope associated with a multivariate polynomial. It can be used to analyze the polynomial's behavior when specific variables are considered negligible relative to the others. Specifically, give ...
s of multivariate polynomials are convex hulls of points derived from the exponents of the terms in the polynomial, and can be used to analyze the
asymptotic In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
behavior of the polynomial and the valuations of its roots. Convex hulls and polynomials also come together in the
Gauss–Lucas theorem In complex analysis, a branch of mathematics, the Gauss–Lucas theorem gives a geometric relation between the roots of a polynomial ''P'' and the roots of its derivative ''P′''. The set of roots of a real or complex polynomial is a set of poin ...
, according to which the
roots A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusing ...
of the derivative of a polynomial all lie within the convex hull of the roots of the polynomial. In spectral analysis, the
numerical range In the mathematical field of linear algebra and convex analysis, the numerical range or field of values of a complex n \times n matrix ''A'' is the set :W(A) = \left\ where \mathbf^* denotes the conjugate transpose of the vector \mathbf. The nume ...
of a
normal matrix In mathematics, a complex square matrix is normal if it commutes with its conjugate transpose : The concept of normal matrices can be extended to normal operators on infinite dimensional normed spaces and to normal elements in C*-algebras. As ...
is the convex hull of its
eigenvalue In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
s. The Russo–Dye theorem describes the convex hulls of
unitary element In mathematics, an element ''x'' of a *-algebra is unitary if it satisfies x^* = x^. In functional analysis, a linear operator ''A'' from a Hilbert space into itself is called unitary if it is invertible and its inverse is equal to its own adjo ...
s in a
C*-algebra In mathematics, specifically in functional analysis, a C∗-algebra (pronounced "C-star") is a Banach algebra together with an involution satisfying the properties of the adjoint. A particular case is that of a complex algebra ''A'' of continuous ...
. In
discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geome ...
, both
Radon's theorem In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of ''d'' + 2 points in R''d'' can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these conve ...
and
Tverberg's theorem In discrete geometry, Tverberg's theorem, first stated by , is the result that sufficiently many points in ''d''-dimensional Euclidean space can be partitioned into subsets with intersecting convex hulls. Specifically, for any set of :(d + 1)(r - ...
concern the existence of partitions of point sets into subsets with intersecting convex hulls. The definitions of a convex set as containing line segments between its points, and of a convex hull as the intersection of all convex supersets, apply to
hyperbolic space In mathematics, hyperbolic space of dimension n is the unique simply connected, n-dimensional Riemannian manifold of constant sectional curvature equal to -1. It is homogeneous, and satisfies the stronger property of being a symmetric space. Th ...
s as well as to Euclidean spaces. However, in hyperbolic space, it is also possible to consider the convex hulls of sets of
ideal point In hyperbolic geometry, an ideal point, omega point or point at infinity is a well-defined point outside the hyperbolic plane or space. Given a line ''l'' and a point ''P'' not on ''l'', right- and left-limiting parallels to ''l'' through ''P'' ...
s, points that do not belong to the hyperbolic space itself but lie on the boundary of a model of that space. The boundaries of convex hulls of ideal points of three-dimensional hyperbolic space are analogous to
ruled surface In geometry, a surface is ruled (also called a scroll) if through every point of there is a straight line that lies on . Examples include the plane, the lateral surface of a cylinder or cone, a conical surface with elliptical directrix, the ...
s in Euclidean space, and their metric properties play an important role in the
geometrization conjecture In mathematics, Thurston's geometrization conjecture states that each of certain three-dimensional topological spaces has a unique geometric structure that can be associated with it. It is an analogue of the uniformization theorem for two-dimensi ...
in
low-dimensional topology In mathematics, low-dimensional topology is the branch of topology that studies manifolds, or more generally topological spaces, of four or fewer dimensions. Representative topics are the structure theory of 3-manifolds and 4-manifolds, knot th ...
. Hyperbolic convex hulls have also been used as part of the calculation of
canonical The adjective canonical is applied in many contexts to mean "according to the canon" the standard, rule or primary source that is accepted as authoritative for the body of knowledge or literature in that context. In mathematics, "canonical example ...
triangulations of
hyperbolic manifold In mathematics, a hyperbolic manifold is a space where every point looks locally like hyperbolic space of some dimension. They are especially studied in dimensions 2 and 3, where they are called hyperbolic surfaces and hyperbolic 3-manifolds, res ...
s, and applied to determine the equivalence of
knots A knot is a fastening in rope or interwoven lines. Knot may also refer to: Places * Knot, Nancowry, a village in India Archaeology * Knot of Isis (tyet), symbol of welfare/life. * Minoan snake goddess figurines#Sacral knot Arts, entertainme ...
. See also the section on
Brownian motion Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas). This pattern of motion typically consists of random fluctuations in a particle's position insi ...
for the application of convex hulls to this subject, and the section on
space curves In mathematics, a curve (also called a curved line in older texts) is an object similar to a line, but that does not have to be straight. Intuitively, a curve may be thought of as the trace left by a moving point. This is the definition that ap ...
for their application to the theory of
developable surface In mathematics, a developable surface (or torse: archaic) is a smooth surface with zero Gaussian curvature. That is, it is a surface that can be flattened onto a plane without distortion (i.e. it can be bent without stretching or compression). ...
s.


Statistics

In
robust statistics Robust statistics are statistics with good performance for data drawn from a wide range of probability distributions, especially for distributions that are not normal. Robust statistical methods have been developed for many common problems, suc ...
, the convex hull provides one of the key components of a
bagplot A bagplot, or starburst plot, is a method in robust statistics for visualizing two- or three-dimensional statistical data, analogous to the one-dimensional box plot. Introduced in 1999 by Rousseuw et al., the bagplot allows one to visualize the l ...
, a method for visualizing the spread of two-dimensional sample points. The contours of
Tukey depth In computational geometry, the Tukey depth is a measure of the depth of a point in a fixed set of points. The concept is named after its inventor, John Tukey. Given a set of points P in ''d''-dimensional space, a point ''p'' has Tukey depth ''k' ...
form a nested family of convex sets, with the convex hull outermost, and the bagplot also displays another polygon from this nested family, the contour of 50% depth. In statistical
decision theory Decision theory (or the theory of choice; not to be confused with choice theory) is a branch of applied probability theory concerned with the theory of making decisions based on assigning probabilities to various factors and assigning numerical ...
, the risk set of a randomized decision rule is the convex hull of the risk points of its underlying deterministic decision rules.


Combinatorial optimization

In
combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
and
polyhedral combinatorics Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral comb ...
, central objects of study are the convex hulls of
indicator vector In mathematics, the indicator vector or characteristic vector or incidence vector of a subset ''T'' of a Set (mathematics), set ''S'' is the vector x_T := (x_s)_ such that x_s = 1 if s \in T and x_s = 0 if s \notin T. If ''S'' is countable set, cou ...
s of solutions to a combinatorial problem. If the facets of these polytopes can be found, describing the polytopes as intersections of halfspaces, then algorithms based on
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
can be used to find optimal solutions. In
multi-objective optimization Multi-objective optimization (also known as multi-objective programming, vector optimization, multicriteria optimization, multiattribute optimization or Pareto optimization) is an area of multiple criteria decision making that is concerned with ...
, a different type of convex hull is also used, the convex hull of the weight vectors of solutions. One can maximize any quasiconvex combination of weights by finding and checking each convex hull vertex, often more efficiently than checking all possible solutions.


Economics

In the
Arrow–Debreu model In mathematical economics, the Arrow–Debreu model suggests that under certain economic assumptions (convex preferences, perfect competition, and demand independence) there must be a set of prices such that aggregate supplies will equal aggreg ...
of general economic equilibrium, agents are assumed to have convex
budget set In economics, a budget set, or the opportunity set facing a consumer, is the set of all possible consumption bundles that the consumer can afford taking as given the prices of commodities available to the consumer and the consumer's income. Let the ...
s and
convex preferences In economics, convex preferences are an individual's ordering of various outcomes, typically with regard to the amounts of various goods consumed, with the property that, roughly speaking, "averages are better than the extremes". The concept roughly ...
. These assumptions of
convexity in economics Convexity is an important topic in economics. In the Arrow–Debreu model of general economic equilibrium, agents have convex budget sets and convex preferences: At equilibrium prices, the budget hyperplane supports the best attainable indiffer ...
can be used to prove the existence of an equilibrium. When actual economic data is non-convex, it can be made convex by taking convex hulls. The Shapley–Folkman theorem can be used to show that, for large markets, this approximation is accurate, and leads to a "quasi-equilibrium" for the original non-convex market.


Geometric modeling

In
geometric modeling __NOTOC__ Geometric modeling is a branch of applied mathematics and computational geometry that studies methods and algorithms for the mathematical description of shapes. The shapes studied in geometric modeling are mostly two- or three-dimensi ...
, one of the key properties of a
Bézier curve A Bézier curve ( ) is a parametric curve used in computer graphics and related fields. A set of discrete "control points" defines a smooth, continuous curve by means of a formula. Usually the curve is intended to approximate a real-world shape t ...
is that it lies within the convex hull of its control points. This so-called "convex hull property" can be used, for instance, in quickly detecting intersections of these curves. In the geometry of boat and ship design,
chain girth Chain girth is a measurement of a yacht hull. Chain girth is specified in some design rules to handicap or match the capabilities of sailing vessels of similar design such as the 12 metre boats. Chain girth is measured as a straight line from ...
is a measurement of the size of a sailing vessel, defined using the convex hull of a cross-section of the
hull Hull may refer to: Structures * Chassis, of an armored fighting vehicle * Fuselage, of an aircraft * Hull (botany), the outer covering of seeds * Hull (watercraft), the body or frame of a ship * Submarine hull Mathematics * Affine hull, in affi ...
of the vessel. It differs from the
skin girth {{unreferenced, date=January 2018 Skin girth is a measurement of a yacht hull. Skin girth is specified in some design rules to handicap or match the capabilities of sailing vessels of similar design such as the 12 metre The 12 Metre class is ...
, the perimeter of the cross-section itself, except for boats and ships that have a convex hull.


Ethology

The convex hull is commonly known as the minimum convex polygon in
ethology Ethology is the scientific study of animal behaviour, usually with a focus on behaviour under natural conditions, and viewing behaviour as an evolutionarily adaptive trait. Behaviourism as a term also describes the scientific and objectiv ...
, the study of animal behavior, where it is a classic, though perhaps simplistic, approach in estimating an animal's
home range A home range is the area in which an animal lives and moves on a periodic basis. It is related to the concept of an animal's territory which is the area that is actively defended. The concept of a home range was introduced by W. H. Burt in 1943. He ...
based on points where the animal has been observed.
Outlier In statistics, an outlier is a data point that differs significantly from other observations. An outlier may be due to a variability in the measurement, an indication of novel data, or it may be the result of experimental error; the latter are ...
s can make the minimum convex polygon excessively large, which has motivated relaxed approaches that contain only a subset of the observations, for instance by choosing one of the convex layers that is close to a target percentage of the samples, or in the
local convex hull Local convex hull (LoCoH) is a method for estimating size of the home range of an animal or a group of animals (e.g. a pack of wolves, a pride of lions, or herd of buffaloes), and for constructing a utilization distribution. The latter is a probabi ...
method by combining convex hulls of
neighborhoods A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; American and British English spelling differences, see spelling differences) is a geographically localised community ...
of points.


Quantum physics

In
quantum physics Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, qua ...
, the
state space A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory. For instance, the toy ...
of any quantum system — the set of all ways the system can be prepared — is a convex hull whose extreme points are positive-semidefinite operators known as pure states and whose interior points are called mixed states. The
Schrödinger–HJW theorem In quantum information theory and quantum optics, the Schrödinger–HJW theorem is a result about the realization of a mixed state of a quantum system as an ensemble of pure quantum states and the relation between the corresponding purifications o ...
proves that any mixed state can in fact be written as a convex combination of pure states in multiple ways.


Thermodynamics

A convex hull in
thermodynamics Thermodynamics is a branch of physics that deals with heat, work, and temperature, and their relation to energy, entropy, and the physical properties of matter and radiation. The behavior of these quantities is governed by the four laws of the ...
was identified by
Josiah Willard Gibbs Josiah Willard Gibbs (; February 11, 1839 – April 28, 1903) was an American scientist who made significant theoretical contributions to physics, chemistry, and mathematics. His work on the applications of thermodynamics was instrumental in t ...
(1873), although the paper was published before the convex hull was so named. In a set of energies of several
stoichiometries Stoichiometry refers to the relationship between the quantities of reactants and products before, during, and following chemical reactions. Stoichiometry is founded on the law of conservation of mass where the total mass of the reactants equals ...
of a material, only those measurements on the lower convex hull will be stable. When removing a point from the hull and then calculating its distance to the hull, its distance to the new hull represents the degree of stability of the phase.


History

The lower convex hull of points in the plane appears, in the form of a Newton polygon, in a letter from
Isaac Newton Sir Isaac Newton (25 December 1642 – 20 March 1726/27) was an English mathematician, physicist, astronomer, alchemist, theologian, and author (described in his time as a "natural philosopher"), widely recognised as one of the grea ...
to
Henry Oldenburg Henry Oldenburg (also Henry Oldenbourg) FRS (c. 1618 as Heinrich Oldenburg – 5 September 1677), was a German theologian, diplomat, and natural philosopher, known as one of the creators of modern scientific peer review. He was one of the for ...
in 1676. The term "convex hull" itself appears as early as the work of , and the corresponding term in
German German(s) may refer to: * Germany (of or related to) **Germania (historical use) * Germans, citizens of Germany, people of German ancestry, or native speakers of the German language ** For citizens of Germany, see also German nationality law **Ger ...
appears earlier, for instance in
Hans Rademacher Hans Adolph Rademacher (; 3 April 1892, Wandsbeck, now Hamburg-Wandsbek – 7 February 1969, Haverford, Pennsylvania, USA) was a German-born American mathematician, known for work in mathematical analysis and number theory. Biography Rademacher r ...
's review of . Other terms, such as "convex envelope", were also used in this time frame.See, e.g., , page 520. By 1938, according to
Lloyd Dines Lloyd Lyne Dines (29 March 1885, in Shelbyville, Missouri – 17 January 1964, in Quincy, Illinois) was an American-Canadian mathematician, known for his pioneering work on linear inequalities.
, the term "convex hull" had become standard; Dines adds that he finds the term unfortunate, because the colloquial meaning of the word "hull" would suggest that it refers to the surface of a shape, whereas the convex hull includes the interior and not just the surface.


Notes


References

* * * * * * * * * * * * * * * * * * * * * * * * * *; reprinted in
The Scientific Papers of J. Willard Gibbs, Vol. I: Thermodynamics
', Longmans, Green, & Co., 1906
pp. 33–54
* * * * *; se
p. 143
* * * * * * * * * *; see also review by
Hans Rademacher Hans Adolph Rademacher (; 3 April 1892, Wandsbeck, now Hamburg-Wandsbek – 7 February 1969, Haverford, Pennsylvania, USA) was a German-born American mathematician, known for work in mathematical analysis and number theory. Biography Rademacher r ...
(1922), * * * * * * * * * * * * * * * * * * * * * * * * *, translated in ''Journal of Soviet Mathematics'' 33 (4): 1140–1153, 1986, * * * * * * * * * * *


External links

* *
"Convex Hull"
by
Eric W. Weisstein Eric Wolfgang Weisstein (born March 18, 1969) is an American mathematician and encyclopedist who created and maintains the encyclopedias ''MathWorld'' and ''ScienceWorld''. In addition, he is the author of the '' CRC Concise Encyclopedia of M ...
,
Wolfram Demonstrations Project The Wolfram Demonstrations Project is an organized, open-source collection of small (or medium-size) interactive programs called Demonstrations, which are meant to visually and interactively represent ideas from a range of fields. It is hos ...
, 2007. {{Convex analysis and variational analysis, state=collapsed Closure operators Convex analysis Computational geometry Geometry processing