Namespaces
Variants
Actions

Difference between revisions of "Convex set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX done)
(→‎Comments: better)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{TEX|done}}
 
{{TEX|done}}
  
''in a Euclidean or in another vector space''
+
''in a [[Euclidean space|Euclidean]] or in another [[vector space]]''
  
 
A set containing with two arbitrary points all points of the segment connecting these points. The intersection of any family of convex sets is itself a convex set.
 
A set containing with two arbitrary points all points of the segment connecting these points. The intersection of any family of convex sets is itself a convex set.
  
The smallest dimension of a plane (i.e. affine subspace) containing a given convex set is called the dimension of that set. The closure of a convex set (i.e. the result of adding to the convex set all its boundary points) yields a convex set of the same dimension. The principal subject of the theory of convex sets is the study of convex bodies, which are finite (i.e. bounded) convex sets of dimension $n$. If boundedness is not stipulated, one speaks of infinite convex bodies, and if the dimension $n$ is not stipulated, one speaks of degenerate convex bodies or of convex bodies of lower dimension.
+
The smallest dimension of a plane (i.e. affine subspace) containing a given convex set is called the dimension of that set. The closure of a convex set (i.e. the result of adding to the convex set all its boundary points) yields a convex set of the same dimension. The principal subject of the theory of convex sets is the study of [[convex body|convex bodies]], which are finite (i.e. bounded) convex sets of dimension $n$. If boundedness is not stipulated, one speaks of infinite convex bodies, and if the dimension $n$ is not stipulated, one speaks of degenerate convex bodies or of convex bodies of lower dimension.
  
 
A convex body is homeomorphic to a closed ball. An infinite convex body not containing straight lines is homeomorphic to a half-space, while those containing a straight line are cylinders with a convex (possibly, infinite) cross-section.
 
A convex body is homeomorphic to a closed ball. An infinite convex body not containing straight lines is homeomorphic to a half-space, while those containing a straight line are cylinders with a convex (possibly, infinite) cross-section.
  
Through each point of the boundary of a convex set there passes at least one hyperplane such that the convex set lies in one of the two closed half-spaces defined by this hyperplane. Such hyperplanes and such half-spaces are called supporting for this set at the given point of the boundary. A closed convex set is the intersection of its supporting half-spaces. The intersection of a finite number of closed half-spaces is a convex polyhedron. The faces of a convex body are its intersections with the supporting hyperplanes. A face is a convex body of lower dimension. The convex body is considered to be its own $n$-dimensional face. As distinct from a polyhedron, a face of a face need not be a face of the initial convex body.
+
Through each point of the boundary of a convex set there passes at least one [[hyperplane]] such that the convex set lies in one of the two closed half-spaces defined by this hyperplane. Such hyperplanes and such half-spaces are called supporting for this set at the given point of the boundary. A closed convex set is the intersection of its supporting half-spaces. The intersection of a finite number of closed half-spaces is a convex polyhedron. The [[face|faces]] of a convex body are its intersections with the [[supporting hyperplane|supporting hyperplanes]]. A face is a convex body of lower dimension. The convex body is considered to be its own $n$-dimensional face. As distinct from a [[polyhedron]], a face of a face need not be a face of the initial convex body.
  
With each boundary point $x$ of a convex body is connected: an open tangent cone, filled by the rays issuing from $x$ and passing through interior points of the convex body; the closed tangent cone, which is its closure; and the surface tangent cone which is its boundary. The two first-mentioned cones are convex.
+
With each boundary point $x$ of a convex body is connected: an open [[tangent cone]], filled by the rays issuing from $x$ and passing through interior points of the convex body; the closed tangent cone, which is its closure; and the surface tangent cone which is its boundary. The two first-mentioned cones are convex.
  
 
The points of the boundary of a convex body are classified by the minimal dimension of the faces to which they belong, and also by the dimension of the set of supporting hyperplanes at the point. The points of zero-dimensional faces are called exposed points. Extremal points of a convex body are points which are not interior to any segment belonging to that convex body. The problem of the possible abundance of points and of the set of directions of faces of various types is being studied. For instance, the points with a non-unique supporting hyperplane have zero $(n-1)$-dimensional area on the boundary; the directions of the segments lying on the boundary have measure zero among all directions in space.
 
The points of the boundary of a convex body are classified by the minimal dimension of the faces to which they belong, and also by the dimension of the set of supporting hyperplanes at the point. The points of zero-dimensional faces are called exposed points. Extremal points of a convex body are points which are not interior to any segment belonging to that convex body. The problem of the possible abundance of points and of the set of directions of faces of various types is being studied. For instance, the points with a non-unique supporting hyperplane have zero $(n-1)$-dimensional area on the boundary; the directions of the segments lying on the boundary have measure zero among all directions in space.
Line 17: Line 17:
 
Each point not belonging to a convex body is strictly separated from it by a hyperplane such that this point and the convex body are in distinct open half-spaces. Two non-intersecting convex sets are separated by a hyperplane, leaving them in different closed half-spaces. This separation property is retained in the case of convex sets in infinite-dimensional vector spaces.
 
Each point not belonging to a convex body is strictly separated from it by a hyperplane such that this point and the convex body are in distinct open half-spaces. Two non-intersecting convex sets are separated by a hyperplane, leaving them in different closed half-spaces. This separation property is retained in the case of convex sets in infinite-dimensional vector spaces.
  
A convex body $F$ has associated with it its support function $H\colon E^n \rightarrow E^1$, defined by the equation $H(u)=\sup\{ux\colon x\in F\}$, where $ux$ is the scalar product. The function $H(u)$ is positively homogeneous of the first degree: $H(\alpha u)=\alpha Hu$ for $\alpha\geq 0$, and is convex:
+
A convex body $F$ has associated with it its [[support function]] $H\colon E^n \rightarrow E^1$, defined by the equation $H(u)=\sup\{ux\colon x\in F\}$, where $ux$ is the scalar product. The function $H(u)$ is positively homogeneous of the first degree: $H(\alpha u)=\alpha Hu$ for $\alpha\geq 0$, and is convex:
 
\begin{equation} H(u+v)\leq H(u) + H(v). \end{equation}
 
\begin{equation} H(u+v)\leq H(u) + H(v). \end{equation}
  
Line 26: Line 26:
 
under the assumption that $D(0)=0$. This is also a positively homogeneous convex function of the first degree, defining $F$. Two convex bodies are called polar (or dual) with respect to each other if the support function of one is the distance function of the other. The existence of dual convex bodies is connected with the self-duality of $E^n$.
 
under the assumption that $D(0)=0$. This is also a positively homogeneous convex function of the first degree, defining $F$. Two convex bodies are called polar (or dual) with respect to each other if the support function of one is the distance function of the other. The existence of dual convex bodies is connected with the self-duality of $E^n$.
  
If a convex body $F$ is symmetric with respect to the coordinate origin, the function $\rho(u,v)=D(u-v)$ is a metric. This is the metric of the Minkowski space (of a finite-dimensional Banach space), $F$ playing the role of the unit ball. In a similar manner, the unit ball in an infinite-dimensional Banach space is a convex set. The properties of the space are connected with the geometry of this ball, in particular with the presence of points of different types on its boundary [[#References|[3]]].
+
If a convex body $F$ is symmetric with respect to the coordinate origin, the function $\rho(u,v)=D(u-v)$ is a metric. This is the metric of the [[Minkowski space]] (of a finite-dimensional [[Banach space]]), $F$ playing the role of the unit ball. In a similar manner, the unit ball in an infinite-dimensional Banach space is a convex set. The properties of the space are connected with the geometry of this ball, in particular with the presence of points of different types on its boundary [[#References|[3]]].
  
A convex body may be given as the [[Convex hull|convex hull]] of the points on its boundary or of some of these points.
+
A convex body may be given as the [[convex hull]] of the points on its boundary or of some of these points.
  
There are a number of criteria permitting one to conclude whether or not a set (or any one set from some family) is convex. For instance, if a $C^2$-smooth closed surface in $E^3$ has non-negative Gaussian curvature at all of its points, this surface is the boundary of a convex body; if the intersection of a compact set $F$ in $E^3$ with any plane which leaves $F$ in one half-space is simply connected, $F$ is convex [[#References|[4]]].
+
There are a number of criteria permitting one to conclude whether or not a set (or any one set from some family) is convex. For instance, if a $C^2$-smooth closed surface in $E^3$ has non-negative [[Gaussian curvature]] at all of its points, this surface is the boundary of a convex body; if the intersection of a compact set $F$ in $E^3$ with any plane which leaves $F$ in one half-space is simply connected, $F$ is convex [[#References|[4]]].
  
 
There are many ways of introducing a metric on a set of convex bodies including degenerate convex bodies but not the empty convex body. The Hausdorff metric is the one most commonly used (cf. [[Convex sets, metric space of]]). In this metric each convex body can be approximated by convex polyhedra, and also by convex bodies defined by $P(x_1,\ldots,x_n)\leq0$, where $P$ is a polynomial in the coordinates, and which have positive principal curvatures at all points on the boundary.
 
There are many ways of introducing a metric on a set of convex bodies including degenerate convex bodies but not the empty convex body. The Hausdorff metric is the one most commonly used (cf. [[Convex sets, metric space of]]). In this metric each convex body can be approximated by convex polyhedra, and also by convex bodies defined by $P(x_1,\ldots,x_n)\leq0$, where $P$ is a polynomial in the coordinates, and which have positive principal curvatures at all points on the boundary.
  
A convex body always has a finite volume (in the sense of Jordan), which is identical with its $n$-dimensional Lebesgue measure. The boundary of a convex body has finite $(n-1)$-dimensional area, and the various ways of introducing an area in such a case are equivalent. The volume and the area of the boundary depend continuously (in the Hausdorff metric) on the convex body.
+
A convex body always has a finite volume (in the sense of [[Jordan measure|Jordan]]), which is identical with its $n$-dimensional [[Lebesgue measure]]. The boundary of a convex body has finite $(n-1)$-dimensional area, and the various ways of introducing an area in such a case are equivalent. The volume and the area of the boundary depend continuously (in the [[Hausdorff metric]]) on the convex body.
  
[[Mixed-volume theory]] is connected with the study of the dependence of the volume of a linear combination $\sum\lambda_i F_i$ of convex bodies on the coefficients $\lambda_i$. Mixed volumes include not only the volume and the area of the boundary, but also many other functionals connected with convex bodies [[#References|[5]]], such as $k$-dimensional volumes of projections in different directions on $k$-dimensional planes and their average values. The principal results of this theory are various inequalities between mixed volumes, including the classical isoperimetric inequality (cf. [[Isoperimetric inequality, classical]]).
+
[[Mixed-volume theory]] is connected with the study of the dependence of the volume of a linear combination $\sum\lambda_i F_i$ of convex bodies on the coefficients $\lambda_i$. Mixed volumes include not only the volume and the area of the boundary, but also many other functionals connected with convex bodies [[#References|[5]]], such as $k$-dimensional volumes of projections in different directions on $k$-dimensional planes and their average values. The principal results of this theory are various inequalities between mixed volumes, including the [[Isoperimetric inequality, classical|classical isoperimetric inequality]]).
  
Convex bodies are related to several simple figures. Thus, each convex body has a unique largest (with respect to volume) inscribed and a smallest circumscribed ellipsoid [[#References|[6]]]. Criteria have been found to characterize the balls, ellipsoids and centrally symmetric bodies among other convex bodies [[#References|[1]]], [[#References|[2]]]. Theorems on families of convex sets form a special subject of the theory of convex sets [[#References|[6]]].
+
Convex bodies are related to several simple figures. Thus, each convex body has a unique largest (with respect to volume) inscribed and a smallest circumscribed [[ellipsoid]] [[#References|[6]]]. Criteria have been found to characterize the balls, ellipsoids and centrally symmetric bodies among other convex bodies [[#References|[1]]], [[#References|[2]]]. Theorems on families of convex sets form a special subject of the theory of convex sets [[#References|[6]]].
  
 
The importance of the theory of convex sets lies in the illustrative nature of its methods and results and in the fact that they are general and independent of analytic requirements of smoothness (non-smooth convex bodies often represent solutions of extremal problems).
 
The importance of the theory of convex sets lies in the illustrative nature of its methods and results and in the fact that they are general and independent of analytic requirements of smoothness (non-smooth convex bodies often represent solutions of extremal problems).
Line 58: Line 58:
 
====Comments====
 
====Comments====
  
The polar set of a convex set $X$ in $E^n$ is defined directly by $X^*=\inf\left\{ u\in E^n\colon ux < 1 \quad\forall \square x\in X \right\}$. The support function of $X$ is then also defined by $H(u)=\inf\left\{\rho > 0\colon u\in \rho X^* \right\}$, and similarly the distance function is given by $D(x)=\sup\left\{ux\colon u\in X^*\right\}$. Given the distance function $D(x)$, the corresponding closed convex set is defined by $X=\left\{x\in E^n\colon D(x)\leq 1\right\}$.
+
The [[polar body|polar set]] of a convex set $X$ in $E^n$ is defined directly by $X^*= \left\{ u\in E^n\colon u\cdot x < 1 \ \forall\,x\in X \right\}$. The support function of $X$ is then also defined by $H(u)=\inf\left\{\rho > 0\colon u\in \rho X^* \right\}$, and similarly the distance function is given by $D(x)=\sup\left\{u\cdot x\colon u\in X^*\right\}$. Given the distance function $D(x)$, the corresponding closed convex set is defined by $X=\left\{x\in E^n\colon D(x)\leq 1\right\}$.
 
 
 
 
  
 
====References====
 
====References====

Latest revision as of 17:30, 23 October 2017


in a Euclidean or in another vector space

A set containing with two arbitrary points all points of the segment connecting these points. The intersection of any family of convex sets is itself a convex set.

The smallest dimension of a plane (i.e. affine subspace) containing a given convex set is called the dimension of that set. The closure of a convex set (i.e. the result of adding to the convex set all its boundary points) yields a convex set of the same dimension. The principal subject of the theory of convex sets is the study of convex bodies, which are finite (i.e. bounded) convex sets of dimension $n$. If boundedness is not stipulated, one speaks of infinite convex bodies, and if the dimension $n$ is not stipulated, one speaks of degenerate convex bodies or of convex bodies of lower dimension.

A convex body is homeomorphic to a closed ball. An infinite convex body not containing straight lines is homeomorphic to a half-space, while those containing a straight line are cylinders with a convex (possibly, infinite) cross-section.

Through each point of the boundary of a convex set there passes at least one hyperplane such that the convex set lies in one of the two closed half-spaces defined by this hyperplane. Such hyperplanes and such half-spaces are called supporting for this set at the given point of the boundary. A closed convex set is the intersection of its supporting half-spaces. The intersection of a finite number of closed half-spaces is a convex polyhedron. The faces of a convex body are its intersections with the supporting hyperplanes. A face is a convex body of lower dimension. The convex body is considered to be its own $n$-dimensional face. As distinct from a polyhedron, a face of a face need not be a face of the initial convex body.

With each boundary point $x$ of a convex body is connected: an open tangent cone, filled by the rays issuing from $x$ and passing through interior points of the convex body; the closed tangent cone, which is its closure; and the surface tangent cone which is its boundary. The two first-mentioned cones are convex.

The points of the boundary of a convex body are classified by the minimal dimension of the faces to which they belong, and also by the dimension of the set of supporting hyperplanes at the point. The points of zero-dimensional faces are called exposed points. Extremal points of a convex body are points which are not interior to any segment belonging to that convex body. The problem of the possible abundance of points and of the set of directions of faces of various types is being studied. For instance, the points with a non-unique supporting hyperplane have zero $(n-1)$-dimensional area on the boundary; the directions of the segments lying on the boundary have measure zero among all directions in space.

Each point not belonging to a convex body is strictly separated from it by a hyperplane such that this point and the convex body are in distinct open half-spaces. Two non-intersecting convex sets are separated by a hyperplane, leaving them in different closed half-spaces. This separation property is retained in the case of convex sets in infinite-dimensional vector spaces.

A convex body $F$ has associated with it its support function $H\colon E^n \rightarrow E^1$, defined by the equation $H(u)=\sup\{ux\colon x\in F\}$, where $ux$ is the scalar product. The function $H(u)$ is positively homogeneous of the first degree: $H(\alpha u)=\alpha Hu$ for $\alpha\geq 0$, and is convex: \begin{equation} H(u+v)\leq H(u) + H(v). \end{equation}

All functions with these two properties are support functions for some unique convex body. Specifying the support function is one of the principal methods of specifying a convex body.

If the coordinate origin is located inside a convex body, one introduces a distance function $D\colon E^n \rightarrow E^1$, which, for $u\neq 0$, is defined by the equation \begin{equation} D(u)=\inf\left\{\alpha\colon\frac{u}{\alpha}\in F\right\}, \end{equation} under the assumption that $D(0)=0$. This is also a positively homogeneous convex function of the first degree, defining $F$. Two convex bodies are called polar (or dual) with respect to each other if the support function of one is the distance function of the other. The existence of dual convex bodies is connected with the self-duality of $E^n$.

If a convex body $F$ is symmetric with respect to the coordinate origin, the function $\rho(u,v)=D(u-v)$ is a metric. This is the metric of the Minkowski space (of a finite-dimensional Banach space), $F$ playing the role of the unit ball. In a similar manner, the unit ball in an infinite-dimensional Banach space is a convex set. The properties of the space are connected with the geometry of this ball, in particular with the presence of points of different types on its boundary [3].

A convex body may be given as the convex hull of the points on its boundary or of some of these points.

There are a number of criteria permitting one to conclude whether or not a set (or any one set from some family) is convex. For instance, if a $C^2$-smooth closed surface in $E^3$ has non-negative Gaussian curvature at all of its points, this surface is the boundary of a convex body; if the intersection of a compact set $F$ in $E^3$ with any plane which leaves $F$ in one half-space is simply connected, $F$ is convex [4].

There are many ways of introducing a metric on a set of convex bodies including degenerate convex bodies but not the empty convex body. The Hausdorff metric is the one most commonly used (cf. Convex sets, metric space of). In this metric each convex body can be approximated by convex polyhedra, and also by convex bodies defined by $P(x_1,\ldots,x_n)\leq0$, where $P$ is a polynomial in the coordinates, and which have positive principal curvatures at all points on the boundary.

A convex body always has a finite volume (in the sense of Jordan), which is identical with its $n$-dimensional Lebesgue measure. The boundary of a convex body has finite $(n-1)$-dimensional area, and the various ways of introducing an area in such a case are equivalent. The volume and the area of the boundary depend continuously (in the Hausdorff metric) on the convex body.

Mixed-volume theory is connected with the study of the dependence of the volume of a linear combination $\sum\lambda_i F_i$ of convex bodies on the coefficients $\lambda_i$. Mixed volumes include not only the volume and the area of the boundary, but also many other functionals connected with convex bodies [5], such as $k$-dimensional volumes of projections in different directions on $k$-dimensional planes and their average values. The principal results of this theory are various inequalities between mixed volumes, including the classical isoperimetric inequality).

Convex bodies are related to several simple figures. Thus, each convex body has a unique largest (with respect to volume) inscribed and a smallest circumscribed ellipsoid [6]. Criteria have been found to characterize the balls, ellipsoids and centrally symmetric bodies among other convex bodies [1], [2]. Theorems on families of convex sets form a special subject of the theory of convex sets [6].

The importance of the theory of convex sets lies in the illustrative nature of its methods and results and in the fact that they are general and independent of analytic requirements of smoothness (non-smooth convex bodies often represent solutions of extremal problems).


References

[1] T. Bonnesen, W. Fenchel, "Theorie der konvexen Körper" , Springer (1934)
[2] F. Valentine, "Convex sets" , McGraw-Hill (1964)
[3] M.M. Day, "Normed linear spaces" , Springer (1958)
[4] Yu.D. Burago, V.A. Zalgaller, "Sufficient conditions of convexity" J. Soviet Math. , 16 : 3 (1978) pp. 395–434 Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. , 45 (1974) pp. 3–53
[5] H. Hadwiger, "Vorlesungen über Inhalt, Oberfläche und Isoperimetrie" , Springer (1957)
[6] L. Danzer, B. Grünbaum, V.L. Klee, "Helly's theorem and its relatives" , Proc. Symp. Pure Math. , 7 , Amer. Math. Soc. (1963) pp. 101–180


Comments

The polar set of a convex set $X$ in $E^n$ is defined directly by $X^*= \left\{ u\in E^n\colon u\cdot x < 1 \ \forall\,x\in X \right\}$. The support function of $X$ is then also defined by $H(u)=\inf\left\{\rho > 0\colon u\in \rho X^* \right\}$, and similarly the distance function is given by $D(x)=\sup\left\{u\cdot x\colon u\in X^*\right\}$. Given the distance function $D(x)$, the corresponding closed convex set is defined by $X=\left\{x\in E^n\colon D(x)\leq 1\right\}$.

References

[a1] H.G. Eggleston, "Convexity" , Cambridge Univ. Press (1969)
How to Cite This Entry:
Convex set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Convex_set&oldid=38654
This article was adapted from an original article by Yu.D. BuragoV.A. Zalgaller (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article