Convex hull: Difference between revisions

Revision as of 20:40, 3 March 2025

Latest revision as of 01:04, 1 July 2025

(4 intermediate revisions by 4 users not shown)

Line 44:

===Preservation of topological properties===

[[File:Versiera007.svg|thumb|The [[witch of Agnesi]]. The points on or above the red curve provide an example of a closed set whose convex hull is open (the open [[upper half-plane]]).]]

Topologically, the convex hull of an [[open set]] is always itself open, and (in Euclidean spaces) the convex hull of a compact set is always itself compact. However, there exist closed sets for which the convex hull is not closed.<ref>{{harvtxt|Grünbaum|2003}}, p. 16; {{harvtxt|Lay|1982}}, p. 21; {{harvtxt|Sakuma|1977}}.</ref> For instance, the closed set

:<math>\left \{ (x,y) \mathop{\bigg|} y\ge \frac{1}{1+x^2}\right\}</math>

Line 50:

(the set of points that lie on or above the [[witch of Agnesi]]) has the open [[upper half-plane]] as its convex hull.<ref>This example is given by {{harvtxt|Talman|1977}}, Remark 2.6.</ref>

TheConvex hulls can be defined more generally in infinite-dimensional [[topological vector space]]s, but they may not preserve compactness in these spaces. Instead, 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]] (a subset that is compact under the [[weak topology]]) is weakly compact.{{sfnp|Whitley|1986}}

===Extreme points===

Line 84:

===Simple polygons===

{{main|Convex hull of a simple polygon}}

[[File:Convex hull of a simple polygon.svg|thumb|upright|Convex hull ( in blue and yellow) of a simple polygon (in blue)]]

The convex hull of a [[simple polygon]] 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]] 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''.{{sfnp|Rappoport|1992}} 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]] states that this expansion process eventually terminates.{{sfnp|Demaine|Gassend|O'Rourke|Toussaint|2008}}

Line 137:

== Applications ==

[[File:CIE1931xy_gamut_comparison.svg|thumb|The convex hull of the primary colors in each [[color space]] on a [[CIE 1931]] xy [[chromaticity diagram]] defines the space's [[gamut]] of possible colors]]

Convex hulls have wide applications in many fields. Within mathematics, convex hulls are used to study [[polynomial]]s, matrix [[eigenvalue]]s, and [[unitary element]]s, and several theorems in [[discrete geometry]] involve convex hulls. They are used in [[robust statistics]] as the outermost contour of [[Tukey depth]], are part of the [[bagplot]] visualization of two-dimensional data, and define risk sets of [[randomised decision rule|randomized decision rule]]s. Convex hulls of [[indicator vector]]s of solutions to combinatorial problems are central to [[combinatorial optimization]] and [[polyhedral combinatorics]]. In economics, convex hulls can be used to apply methods of [[convexity in economics]] to non-convex markets. In geometric modeling, the convex hull property [[Bézier curve]]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]].

===Mathematics===

[[File:Tverberg heptagon.svg|thumb|upright|Partition of seven points into three subsets with intersecting convex hulls, guaranteed to exist for any seven points in the plane by [[Tverberg's theorem]]]]

[[Newton polygon]]s of univariate [[polynomial]]s and [[Newton polytope]]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 analysis|asymptotic]] behavior of the polynomial and the valuations of its roots.<ref>{{harvtxt|Artin|1967}}; {{harvtxt|Gel'fand|Kapranov|Zelevinsky|1994}}</ref> Convex hulls and polynomials also come together in the [[Gauss–Lucas theorem]], according to which the [[Zero of a function|roots]] of the derivative of a polynomial all lie within the convex hull of the roots of the polynomial.{{sfnp|Prasolov|2004}}

[[File:Tverberg heptagon.svg|thumb|upright|Partition of seven points into three subsets with intersecting convex hulls, guaranteed to exist for any seven points in the plane by [[Tverberg's theorem]]]]

In [[Spectral theory|spectral analysis]], the [[numerical range]] of a [[normal matrix]] is the convex hull of its [[eigenvalue]]s.{{sfnp|Johnson|1976}}

The [[Russo–Dye theorem]] describes the convex hulls of [[unitary element]]s in a [[C*-algebra]].{{sfnp|Gardner|1984}}