Convex set - AbsoluteAstronomy.com

Euclidean space

In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

, 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, for example, a crescent

Crescent

In art and symbolism, a crescent is generally the shape produced when a circular disk has a segment of another circle removed from its edge, so that what remains is a shape enclosed by two circular arcs of different diameters which intersect at two points .In astronomy, a crescent...

shape, is not convex.

The notion can be generalized to other spaces as described below.

In vector spaces

Let S be a vector space

Vector space

A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

over the real number

Real number

In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s, or, more generally, some ordered field

Ordered field

In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. Historically, the axiomatization of an ordered field was abstracted gradually from the real numbers, by mathematicians including David Hilbert, Otto Hölder and...

. This includes Euclidean spaces. A set C in S is said to be convex if, for all x and y in C and all t in the interval

Interval (mathematics)

In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...

[0,1], the point
x + t y

is in C. In other words, every point on the line segment

Line segment

In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...

connecting x and y is in C. This implies that a convex set in a real

Real number

In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

or complex

Complex number

A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

topological vector space

Topological vector space

In mathematics, a topological vector space is one of the basic structures investigated in functional analysis...

is path-connected, thus connected

Connected space

In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint nonempty open subsets. Connectedness is one of the principal topological properties that is used to distinguish topological spaces...

.

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

Balanced set

In linear algebra and related areas of mathematics a balanced set, circled set or disk in a vector space is a set S so that for all scalars α with |α| ≤ 1\alpha S \subseteq S...

.

The convex subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of R (the set of real numbers) are simply the intervals of R.
Some examples of convex subsets of Euclidean 2-space

Euclidean space

In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

are regular polygon

Regular polygon

A regular polygon is a polygon that is equiangular and equilateral . Regular polygons may be convex or star.-General properties:...

s and bodies of constant width

Curve of constant width

In geometry, a curve of constant width is a convex planar shape whose width, defined as the perpendicular distance between two distinct parallel lines each intersecting its boundary in a single point, is the same regardless of the direction of those two parallel lines.More generally, any compact...

.
Some examples of convex subsets of Euclidean 3-space

Euclidean space

In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

are the Archimedean solid

Archimedean solid

In geometry an Archimedean solid is a highly symmetric, semi-regular convex polyhedron composed of two or more types of regular polygons meeting in identical vertices...

s and the Platonic solid

Platonic solid

In geometry, a Platonic solid is a convex polyhedron that is regular, in the sense of a regular polygon. Specifically, the faces of a Platonic solid are congruent regular polygons, with the same number of faces meeting at each vertex; thus, all its edges are congruent, as are its vertices and...

s. The Kepler-Poinsot polyhedra are examples of non-convex sets.

Properties

is a convex set, for any

, and any nonnegative numbers

such that

, then the vector

is in

. A vector of this type is known as a convex combination

Convex combination

In convex geometry, a convex combination is a linear combination of points where all coefficients are non-negative and sum up to 1....

Intersections and unions

The collection of convex subsets of a vector space has the following properties:

The empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

and the whole vector-space are convex.
The intersection of any collection of convex sets is convex.
The union of a non-decreasing sequence
Net (mathematics)
In mathematics, more specifically in general topology and related branches, a net or Moore–Smith sequence is a generalization of the notion of a sequence. In essence, a sequence is a function with domain the natural numbers, and in the context of topology, the range of this function is...

of convex subsets is a convex set.

For the preceding property of unions of non-decreasing sequences of convex sets, the restriction to nested sets was important: The union of two convex sets need not be convex.

Convex hulls

Every subset A of the vector space is contained within a smallest convex set (called the convex hull

Convex hull

In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....

of A), namely the intersection of all convex sets containing A.
The convex-hull operator Conv has the characteristic properties of a hull operator

Closure operator

In mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....

extensive	S ⊆ Conv(S),
non-decreasing	S ⊆ T implies that Conv(S) ⊆ Conv(T), and
idempotent Idempotence Idempotence is the property of certain operations in mathematics and computer science, that they can be applied multiple times without changing the result beyond the initial application...	Conv(Conv(S)) = Conv(S).

The convex-hull operation is needed for the set of convex sets to form a lattice

Lattice (order)

In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...

, in which the "join" operation

Join and meet

In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...

is the convex hull of the union of two convex sets

Conv(S)∨Conv(T) = Conv( S ∪ T ) = Conv( Conv(S) ∪ Conv(T) ).

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

Lattice (order)

Minkowski addition

In a real vector-space, the Minkowski sum
Minkowski addition
In geometry, the Minkowski sum of two sets A and B in Euclidean space is the result of adding every element of A to every element of B, i.e...

of two (non-empty) sets S₁ and S₂ is defined to be the set
Sumset
In additive combinatorics, the sumset of two subsets A and B of an abelian group G is defined to be the set of all sums of an element from A with an element from B...

S₁ + S₂ formed by the addition of vectors element-wise from the summand-sets

S₁ + S₂ = { x₁ + x₂ : x₁ ∈ S₁ and x₂ ∈ S₂ }.

More generally, the Minkowski sum of a finite family of (non-empty) sets S_n is the set formed by element-wise addition of vectors

∑ S_n = { ∑ x_n : x_n ∈ S_n }.

For Minkowski addition, the zero set {0} containing only the zero vector

Null vector

Null vector can refer to:* Null vector * A causal structure in Minkowski space...

0 has special importance

Identity element

In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...

: For every non-empty subset S of a vector space

S + {0} = S;

in algebraic terminology, the zero vector 0 is the identity element

Identity element

In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...

of Minkowski addition (on the collection of non-empty sets).

Convex hulls of Minkowski sums

Minkowski addition behaves well with respect to the operation of taking convex hulls, as shown by the following proposition:

For all subsets S₁ and S₂ of a real vector-space, the convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....

of their Minkowski sum is the Minkowski sum of their convex hulls

Conv( S₁ + S₂ ) = Conv( S₁ ) + Conv( S₂ ).

This result holds more generally for each finite collection of non-empty sets

Conv( ∑ S_n ) = ∑ Conv( S_n ).

In mathematical terminology, the operation

Operation (mathematics)

The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....

s of Minkowski summation and of forming convex hull

Convex hull

In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....

s are commuting

Commutativity

In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...

operations.

Closed convex sets

Closed

Closed set

In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points...

convex sets can be characterised as the intersections of closed half-space
Half-space
In geometry, a half-space is either of the two parts into which a plane divides the three-dimensional euclidean space. More generally, a half-space is either of the two parts into which a hyperplane divides an affine space...

s (sets of point in space that lie on and to one side of a hyperplane

Hyperplane

A hyperplane is a concept in geometry. It is a generalization of the plane into a different number of dimensions.A hyperplane of an n-dimensional space is a flat subset with dimension n − 1...

). 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

Hahn–Banach theorem

In mathematics, the Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear functionals defined on a subspace of some vector space to the whole space, and it also shows that there are "enough" continuous linear functionals defined on every normed...

of functional analysis

Functional analysis

Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure and the linear operators acting upon these spaces and respecting these structures in a suitable sense...

.

The Minkowski sum of two compact convex sets is closed, as is the sum of a compact convex set and a closed convex set.

Generalizations and extensions for 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.

Star-convex sets

Let C be a set in a real or complex vector space. C is star convex if there exists an

in C such that the line segment from

to any point y in C is contained in C. Hence a non-empty convex set is always star-convex but a star-convex set is not always convex.

Orthogonal convexity

An example of generalized convexity is orthogonal convexity.

A set S in the Euclidean space is called orthogonally convex or ortho-convex, 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.

Not Euclidean geometry

The definition of a convex set and a convex hull extends naturally to geometries which are not Euclidean by defining a geodesically convex set

Geodesic convexity

In mathematics — specifically, in Riemannian geometry — geodesic convexity is a natural generalization of convexity for sets and functions to Riemannian manifolds...

to be one that contains the geodesic

Geodesic

In mathematics, a geodesic is a generalization of the notion of a "straight line" to "curved spaces". In the presence of a Riemannian metric, geodesics are defined to be the shortest path between points in the space...

s joining any two points in the set.

Order topology

Convexity can be extended for a space

endowed with the order topology

Order topology

In mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets...

, using the total order

Total order

In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

of the space.

Let

. The subspace

is a convex set if for each pair of points

such that

, the interval

is contained in

. That is,

is convex if and only if

Convexity spaces

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

Axiom

In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...

s.

Given a set X, a convexity over X is a collection

of subsets of X satisfying the following axioms:

The empty set and X are in
The intersection of any collection from is in .
The union of a chain
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

(with respect to the inclusion relation) of elements of is in .

The elements of

are called convex sets and the pair (X,

) 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

Discrete geometry

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles,...

, see the convex geometries associated with antimatroid

Antimatroid

In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included...

External links

Lectures on Convex Sets, notes by Niels Lauritzen, at Aarhus University, March 2010.

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

In vector spaces

Properties

Intersections and unions

Convex hulls

Minkowski addition

Convex hulls of Minkowski sums

Closed convex sets

Generalizations and extensions for convexity

Star-convex sets

Orthogonal convexity

Not Euclidean geometry

Order topology

Convexity spaces

See also

External links