Editing Convex hull (section)

==Definitions==
[[File:ConvexHull.svg|thumb|Convex hull of a bounded planar set: rubber band analogy]]
A set of points in a [[Euclidean space]] is defined to be [[convex set|convex]] if it contains the line segments connecting each pair of its points. The convex hull of a given set <math>X</math> may be defined as{{sfnp|Rockafellar|1970|page=12}}
#The (unique) minimal convex set containing <math>X</math>
#The intersection of all convex sets containing <math>X</math>
#The set of all [[convex combination]]s of points in <math>X</math>
#The union of all [[simplex|simplices]] with vertices in <math>X</math>
For [[bounded set]]s in the Euclidean plane, not all on one line, the boundary of the convex hull is the [[simple closed curve]] with minimum [[perimeter]] containing <math>X</math>. One may imagine stretching a [[rubber band]] so that it surrounds the entire set <math>S</math> and then releasing it, allowing it to contract; when it becomes taut, it encloses the convex hull of <math>S</math>.{{sfnp|de Berg|van Kreveld|Overmars|Schwarzkopf|2008|page=3}} 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]] of the points encloses them with arbitrarily small surface area, smaller than the surface area of the convex hull.<ref>{{harvtxt|Williams|Rossignac|2005}}. See also Douglas Zare, [https://mathoverflow.net/a/166317/440 answer to "the perimeter of a non-convex set"], [[MathOverflow]], May 16, 2014.</ref> However, in higher dimensions, variants of the [[obstacle problem]] of finding a minimum-energy surface above a given shape can have the convex hull as their solution.{{sfnp|Oberman|2007}}

For objects in three dimensions, the first definition states that the convex hull is the smallest possible convex [[bounding volume]] of the objects.
The definition using intersections of convex sets may be extended to [[non-Euclidean geometry]], and the definition using convex combinations may be extended from Euclidean spaces to arbitrary [[real vector space]]s or [[affine space]]s; convex hulls may also be generalized in a more abstract way, to [[oriented matroid]]s.{{sfnp|Knuth|1992}}

===Equivalence of definitions===
[[File:3D_Convex_Hull.tiff|thumb|3D convex hull of 120 point cloud]]
It is not obvious that the first definition makes sense: why should there exist a unique minimal convex set containing <math>X</math>, for every <math>X</math>? However, the second definition, the intersection of all convex sets containing <math>X</math>, is well-defined. It is a subset of every other convex set <math>Y</math> that contains <math>X</math>, because <math>Y</math> is included among the sets being intersected. Thus, it is exactly the unique minimal convex set containing <math>X</math>. Therefore, the first two definitions are equivalent.{{sfnp|Rockafellar|1970|page=12}}

Each convex set containing <math>X</math> must (by the assumption that it is convex) contain all convex combinations of points in <math>X</math>, so the set of all convex combinations is contained in the intersection of all convex sets containing <math>X</math>. Conversely, the set of all convex combinations is itself a convex set containing <math>X</math>, so it also contains the intersection of all convex sets containing <math>X</math>, and therefore the second and third definitions are equivalent.<ref name=rock12lay17>{{harvtxt|Rockafellar|1970}}, p. 12; {{harvtxt|Lay|1982}}, p. 17.</ref>

In fact, according to [[Carathéodory's theorem (convex hull)|Carathéodory's theorem]], if <math>X</math> is a subset of a <math>d</math>-dimensional Euclidean space, every convex combination of finitely many points from <math>X</math> is also a convex combination of at most <math>d+1</math> points in <math>X</math>. The set of convex combinations of a <math>(d+1)</math>-tuple of points is a [[simplex]]; in the plane it is a [[triangle]] and in three-dimensional space it is a tetrahedron. Therefore, every convex combination of points of <math>X</math> belongs to a simplex whose vertices belong to <math>X</math>, and the third and fourth definitions are equivalent.<ref name=rock12lay17/>

===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.<ref>{{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2008}}, p. 6. The idea of partitioning the hull into two chains comes from an efficient variant of [[Graham scan]] by {{harvtxt|Andrew|1979}}.</ref>