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 ...
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'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
, 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 w ...
s of points in the subset. For a bounded 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 su ...
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 ...
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 de ...
, 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 problems or to perform a computation. Algorithms are used as specifications for performing ...
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 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. O ...
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 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 to form a single closed path. If ...
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 ...
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 Cart ...
, convex layers,
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 ...
, 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'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
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 polytop ...
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 w ...
s of points in X #The union of all simplices 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 m ...
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 exteri ...
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 pr ...
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 ...
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 i ...
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 operati ...
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 g ...
, 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 related ...
s; convex hulls may also be generalized in a more abstract way, to oriented matroids.


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 edges and three 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, any three points, when non- colline ...
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 (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 (den ...
) 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 ...
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. T ...
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 octahe ...
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 su ...
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 ...
as its convex hull. The compactness of convex hulls of compact sets, in finite-dimensional Euclidean spaces, is generalized by the
Krein–Smulian theorem In mathematics, particularly in functional analysis, the Krein-Smulian theorem can refer to two theorems relating the closed convex hull and compactness in the weak topology In mathematics, weak topology is an alternative term for certain in ...
, 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 ...
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 ...
) 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'' sho ...
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 de ...
: *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 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 arises in a number of pl ...
'', 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 dua ...
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 w ...
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 are ...
, 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 ...
. 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. O ...
, 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 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 to form a single closed path. If ...
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 ...
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 ...
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, t ...
s. Examples include the oloid, 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 rolle ...
, 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 oth ...
for a surface formed by gluing together two planar convex sets of equal perimeter.


Functions

The convex hull or lower convex envelope 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 the function lies above the graph between the two points. Equivalently, a function is convex if its epigraph (the set of poi ...
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 transformatio ...
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 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'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
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 '' ve ...
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 ...
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 fr ...
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 ...
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 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 f ...
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 characteriz ...
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 ...
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 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 to form a single closed path. If ...
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 connecti ...
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 Cart ...
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 ca ...
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 setti ...
. *The holomorphically convex hull is a generalization of similar concepts to complex analytic manifolds, 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 deriv ...
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, 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 ...
, 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 shapes 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 pol ...
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 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 exampl ...
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 denote ...
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 a ...
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 ge ...
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, su ...
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 ...
visualization of two-dimensional data, and define risk sets of randomized decision rules. Convex hulls of indicator vectors 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 co ...
. 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 ...
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 polygons 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 exampl ...
s and Newton polytopes 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 context ...
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 points ...
, 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 denote ...
s. The
Russo–Dye theorem In mathematics, the Russo–Dye theorem is a result in the field of functional analysis. It states that in a unital C*-algebra, the closure of the convex hull of the unitary elements is the closed unit ball. The theorem was published by B. Rus ...
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 a ...
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 continuou ...
. 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 ge ...
, 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 con ...
and Tverberg's theorem 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. The ...
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 '' ...
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, t ...
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-dimens ...
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 examp ...
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, r ...
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 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, su ...
, 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 ...
, 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 co ...
, central objects of study are the convex hulls of indicator vectors 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 relationships. Linear programming is ...
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 aggregat ...
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-dimensio ...
, 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 ...
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 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, 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 objecti ...
, 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 method by combining convex hulls of neighborhoods 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 to ...
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 ...
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 ...
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 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, Theology, theologian, and author (described in his time as a "natural philosophy, natural philosopher"), widely ...
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 fo ...
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 **Ge ...
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, 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