Convex hull: Difference between revisions

Revision as of 04:05, 29 October 2023

Revision as of 04:06, 29 October 2023

Line 17:

#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>. YouOne 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 Definitionsdefinitions===

[[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}}