Editing Convex hull (section)

{{Short description|Smallest convex set containing a given set}}
{{about|the smallest convex shape enclosing a given shape|boats whose hulls are convex|Hull (watercraft)#Hull shapes}}
{{good article}}
[[File:Extreme points.svg|thumb|right|The convex hull of the red set is the blue and red [[convex set]].]]
In [[geometry]], the '''convex hull''', '''convex envelope''' or '''convex closure'''{{refn|The terminology ''convex closure'' refers to the fact that the convex hull defines a [[closure operator]]. However, this term is also frequently used to refer to the ''closed convex hull'', with which it should not be confused — see e.g {{harvtxt|Fan|1959}}, p.48.}} of a shape is the smallest [[convex set]] 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]], or equivalently as the set of all [[convex combination]]s of points in the subset. For a [[Bounded set|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]]s are open, and convex hulls of [[compact set]]s are compact. Every compact convex set is the convex hull of its [[extreme point]]s. The convex hull operator is an example of a [[closure operator]], and every [[antimatroid]] can be represented by applying this closure operator to finite sets of points.
The [[algorithm]]ic problems of finding the convex hull of a finite set of points in the plane or other low-dimensional Euclidean spaces, and its [[projective duality|dual]] problem of intersecting [[Half-space (geometry)|half-spaces]], are fundamental problems of [[computational geometry]]. They can be solved in time <math>O(n\log n)</math> for two or three dimensional point sets, and in time matching the worst-case output complexity given by the [[upper bound theorem]] in higher dimensions.

As well as for finite point sets, convex hulls have also been studied for [[simple polygon]]s, [[Brownian motion]], [[space curve]]s, and [[Epigraph (mathematics)|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]], [[convex layers]], [[Delaunay triangulation]] and [[Voronoi diagram]], and [[convex skull]].