# Convex sets

Convex sets play an important role in geometry. In order to understand what convex sets are, we need to define and observe convex combinations.

## Convex combinations

Assume we have points $P_{0}, P_{1}, \cdots, P_{n}$. Furthermore, if we choose $\alpha_{0}, \alpha_{1}, \cdots, \alpha_{n}$ such that $0 \leq \alpha_{i} \leq 1, i =0, 1, \cdots, n$ and $\alpha_{0} + \alpha_{1} + \alpha_{2} + \cdots + \alpha_{n} = 1$, we form a new point

$$P = \alpha_{0} P_{0} + \alpha_{1}P_{1} + \cdots + \alpha_{n}P_{n}.$$

Each obtained point $P$ is called a convex combination of points $P_{0}, P_{1}, \cdots, P_{n}$.

For instance, imagine you have two points $P_{0}$, $P_{1}$ and line $P_{0}P_{1}$. Any point $P$ which lies on line $P_{0}P_{1}$ can be written as:

$$P = (1 – \alpha) P_{0} + \alpha P_{1},$$

which is an affine combination of points $P_{0}$ and $P_{1}$.

Convex sets

The point $P$ is a convex combination of points $P_{0}$ and $P_{1}$ because $0 \leq \alpha \leq 1$ and $0 \leq (1 – \alpha) \leq 1$. Moreover, any point on the line segment $\overline{P_{0}P_{1}}$ can be written in this way.

## What is a convex set?

Intuitively, if we can draw a straight line between any two arbitrary points of a set which is not entirely in a set, then the set is non – convex.

We say that the set is convex if any convex combination of two arbitrary points of that set is also an element of that set. More precisely, let $V$ denote a real vector space.

Definition:  Let $a, b \in V$. Then the set of all convex combinations of $a, b$ is the set of points (*) :

$$\{c \in V: c = (1 – \alpha)a + \alpha b, 0 \leq \alpha \leq 1 \}.$$

Definition:  Let $S \subset V$. We say that $S$ is a convex set if for two points $a, b \in S$ the set (*) is a subset of $S$.

In other words, a convex set is a set which contains all possible convex combinations of its points.

## Examples of convex sets

Example 1:  The empty set $\emptyset$, the singleton set $\{x\}$ and space $\mathbb{R^n}$ are convex sets.

Example 2:  Is an interval $[a, b] \subset \mathbb{R}$ a convex set?

Solution:

Let $c, d \in [a, b]$ and assume, without loss of generality, that $c < d$. Furthermore, let $\alpha \in [0, 1]$. Then

$$a \leq c = (1 – \alpha)c + \alpha c < (1 – \alpha)c + \alpha d$$

$$< (1 – \alpha)d + \alpha d = d$$

$$\leq b.$$

In conclusion, an interval $[a, b] \subset \mathbb{R}$ a convex set.

Example 3: Any line or a ray is a convex set, as it contains the line segment between any two of its points.

Example 4: Some polygons are convex, and some are concave.

Any triangle is a convex set. Also, a regular pentagon is a convex set.

Convex sets in $\mathbb{R^2}$ include interiors of triangles, squares, circles, ellipses etc.

Example 5:  The ball $K(x, r)$ is a convex set. More precisely, if we have two vectors $y, z$ within this ball, we can use triangle inequality to show that the line segment $[y, z]$ is also contained within the ball.

Example 6: All regular polyhedra (i.e.) Platonic solids are convex.

## Properties of convex sets

Suppose you have two convex sets $A$ and $B$. Is their intersection a convex set also? Furthermore, is their union a convex set?

Intersection of two convex sets is a convex set.

More precisely, consider two points in the intersection $A \cap B$. Obviously, those points are elements of individual sets $A$ and $B$. Therefore, the line segment which connects them is contained in both $A$ and $B$ and hence in the set $A \cap B$.

Similarly, intersection of finite number of sets (even infinite) is also a convex set.

But, the same property isn’t true for unions. In other words, the union of two convex sets is not necessarily a convex set (picture below).

Example 7: Let $C_{1}, C_{2}$ be convex sets in $\mathbb{R^n}$. Prove that $$C_{1} + C_{2} := \{z \in \mathbb{R^n} : z = x_{1} + x_{2}, x_{1} \in C_{1}, x_{2} \in C_{2}\}$$ is convex.

Solution:

Let $z_{1}, z_{2} \in C_{1} + C_{2}$ and take $0 \leq \alpha \leq 1$. Furthermore, let $z_{1} = x_{1} + x_{2}$, where $x_{1} \in C_{1}, x_{2} \in C_{2}$ and $z_{2} = y_{1} + y_{2}$. Then

$$(1 – \alpha) z_{1} + \alpha z_{2} = (1 – \alpha)[x_{1} + x_{2}] + \alpha [y_{1} + y_{2}]$$

$$= [(1 – \alpha) x_{1} + \alpha y_{1}] + [(1 – \alpha) x_{2} + \alpha y_{2}] \in C_{1} + C_{2},$$

because sets $C_{1}$ and $C_{2}$ are convex.

The sum from Example 7 is called the Minkowski sum of convex sets.

When $C_{2} = \{c\}$ is a singleton, we write the set $C_{1} + \{c\}$ as $C_{1} + c$ and call it the translation of $C_{1}$.

Example 8: Let $A \subseteq \mathbb{R^n}$ be a set and $\alpha \in \mathbb{R}$. We define the scaling $\alpha A \subseteq \mathbb{R^n}$ as

$$\alpha A = \{\alpha x : x \in A\}.$$

When $\alpha > 0$, the set $\alpha A$ is called a dilation of $A$.

Try to prove that if $A$ is convex, then for any $\alpha \in \mathbb{R}$ the set $\alpha A$ is convex.

## Convex hull

Definition: Let $S \subseteq \mathbb{R^n}$. A set of all convex combinations of points from $S$, denoted by $conv S$ is called the convex hull of $S$.

Obviously, a convex hull is a convex set. Moreover, the convex hull of a set $S$ is the smallest convex set which includes $S$.

Some other properties of a convex hull:

$S \subset conv S$

$\forall S’, S’$  convex, $S \subset S’ \rightarrow$ conv$S \subset S’$

Furthermore, any closed convex set $S$ can be written as the convex hull of a possibly infinite set of points $P$: $S =$hull$(T)$.

Indeed, if $S$ is a closed convex set, it is the convex hull of itself.