Convex set

From Wikipedia, the free encyclopedia

Look up Convex set in
Wiktionary, the free dictionary.
For other uses of convex, see convex function and convexity.

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. For example, a solid cube is convex, but anything that is hollow or has a dent in it is not convex.

Contents

[edit] In Euclidean geometry

A convex set.
A convex set.
A non-convex (concave) set.
A non-convex (concave) set.

Let C be a set in a real or complex vector space. C is said to be convex if, for all x and y in C and all t in the interval [0,1], the point

(1 − t) x + t y

is in C. In other words, every point on the line segment connecting x and y is in C. This implies that a convex set is connected.

A set C is called absolutely convex if it is convex and balanced.

The convex subsets of R (the set of real numbers) are simply the intervals of R. Some examples of convex subsets of Euclidean 2-space are regular polygons and bodies of constant width. Some examples of convex subsets of Euclidean 3-space are the Archimedean solids and the Platonic solids. The Kepler-Poinsot polyhedra are examples of non-convex sets.

[edit] Properties

If S is a convex set, for any u_1,u_2,\ldots,u_r in S, and any non negative numbers \lambda_1,\lambda_2,\ldots,\lambda_r such that \lambda_1+\lambda_2+\cdots+\lambda_r=1, then the vector \sum_{k=1}^r\lambda_k u_k is in S. A vector of this type is known as a convex combination of u_1,u_2,\ldots,u_r.

The intersection of any collection of convex sets is itself convex, so the convex subsets of a (real or complex) vector space form a complete lattice. This also means that any subset A of the vector space is contained within a smallest convex set (called the convex hull of A), namely the intersection of all convex sets containing A.

Closed convex sets can be characterised as the intersections of closed half-spaces (sets of point in space that lie on and to one side of a hyperplane). From what has just been said, it is clear that such intersections are convex, and they will also be closed sets. To prove the converse, i.e., every convex set may be represented as such intersection, one needs the supporting hyperplane theorem in the form that for a given closed convex set C and point P outside it, there is a closed half-space H that contains C and not P. The supporting hyperplane theorem is a special case of the Hahn-Banach theorem of functional analysis.

[edit] Star-convex sets

Main article: Star domain

Let C be a set in a real or complex vector space. C is star convex if there exists an x0 in C such that the line segment from x0 to any point y in C is contained in C. Hence a convex set is always star convex but a star-convex object is not always convex.

[edit] In non-Euclidean geometry

The definition of a convex set and a convex hull extends naturally to non-Euclidean geometry by defining a convex set to contain the geodesics joining any two points in the set.

[edit] Generalized convexity

The notion of convexity in the Euclidean space may be generalized by modifying the definition in some or other aspects. The common name "generalized convexity" is used, because the resulting objects retain certain properties of convex sets.

[edit] Orthogonal convexity

An example of generalized convexity is orthogonal convexity.

A set S in the Euclidean space is called orthogonally convex or orthoconvex, if any segment parallel to any of the coordinate axes connecting two points of S lies totally within S. It is easy to prove that an intersection of any collection of orthoconvex sets is orthoconvex. Some other properties of convex sets are valid as well.

[edit] Abstract (axiomatic) convexity

The notion of convexity may be generalised to other objects, if certain properties of convexity are selected as axioms.

Given a set X, a convexity over X is a collection \mathcal{C} of subsets of X satisfying the following axioms:

  1. The empty set and X are in \mathcal{C}
  2. The intersection of any collection from \mathcal{C} is in \mathcal{C}.
  3. The union of a chain (with respect to the inclusion relation) of elements of \mathcal{C} is in \mathcal{C}.

The elements of \mathcal{C} are called convex sets and the pair (X, \mathcal{C})) is called a convexity space. For the ordinary convexity, the first two axioms hold, and the third one is trivial.

For an alternative definition of abstract convexity, more suited to discrete geometry, see the convex geometries associated with antimatroids.

[edit] See also

[edit] References

  • Rawlins G.J.E. and Wood D, "Ortho-convexity and its generalizations", in: Computational Morphology, 137-152. Elsevier, 1988.
  • Soltan, Valeriu, Introduction to the Axiomatic Theory of Convexity, Ştiinţa, Chişinău, 1984 (in Russian).
  • Himmelblau M.D. and Edgar T.E, "Optimization of Chemical Processes", 2nd Edition, 121-151. McGraw-Hill, 2001 (International Edition).
Retrieved from "http://en.wikipedia.org../../../c/o/n/Convex_set.html"