Convex hull

In mathematics, the convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X. For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around X.

Formally, the convex hull may be defined as the intersection of all convex sets containing X or as the set of all convex combinations of points in X. With the latter definition, convex hulls may be extended from Euclidean spaces to arbitrary real vector spaces; they may also be generalized further, to oriented matroids.

The algorithmic problem of finding the convex hull of a finite set of points in the plane or in low-dimensional Euclidean spaces is one of the fundamental problems of computational geometry.



Convex hull of some points in the plane



Convex set

In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object.


A convex set



Convex combination

In convex geometry, 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 up to 1.

More formally, given a finite number of pointsx1, x2, ..., xn in a real vector space, a convex combination of these points is a point of the form



As a particular example, every convex combination of two points lies on the line segment between the points.

All convex combinations are within the convex hull of the given points. In fact, the collection of all such convex combinations of points in the set constitutes the convex hull of the set.

There exist subsets of a vector space that are not closed under linear combinations but are closed under convex combinations. For example, the interval  is convex but generates the real-number line under linear combinations. Another example is the convex set of probability distributions, as linear combinations preserve neither nonnegativity nor affinity (i.e., having total integral one).



Given three points x1, x2, x3 in a plane as shown in the figure,
the point P is a convex combination of the three points, while Q is not.

(Q is however an affine combination of the three points, as their affine hull is the entire plane.)



Simplex

In geometry, a simplex (plural simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, a k-simplex is a k-dimensional polytype which is the convex hull of its k + 1 vertices.

For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron, and a 4-simplex is a 5-cell.

The convex hull of any nonempty subset of the n+1 points that define an n-simplex is called a face of the simplex.


The 15 (= 24 - 1) hyperfaces of the tetrahedron



References


티스토리툴바