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}$.

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

**and space**

*singleton set $\{x\}$***are convex sets.**

*$\mathbb{R^n}$***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

*is a convex set, as it contains the line segment between any two of its points.*

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

Any * triangle* is a convex set. Also, a

**is a convex set.**

*regular pentagon*

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

*to show that the line segment $[y, z]$ is also contained within the ball.*

**triangle inequality****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

*of $S$.*

**convex hull**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.