# How to find the convex hull of a given set?

• $A=\{(0,0),(0,1),(1,0)\}$
• $B=\mathbb{Q}^2$
• $C=\{(x,\sqrt{x})\in \mathbb{R}^2:x\ge0\}$

I have to find Conv(A), Conv(B) and Conv(C).

My attempt

Conv(A) is the boundary (correction: obviously it isn't just the boundary) of the triangle that has vertices in $(0,0),(0,1),(1,0)$

Conv(B) is $\mathbb{R}^2$ (we use the fact, that $\mathbb{Q}^2$ is dense in $\mathbb{R}^2$.

And I'm not sure about the last one, but my guess is:

Conv(C) $= \{(x,y)\in\mathbb{R}^2:x\ge0, \:\: 0\le y\le\sqrt{x}\}$

Is that correct? If so, how can I formally show it?

• Show that any point in that set lies on a straight line from the origin to a point on the graph.
– M.B.
Commented Oct 6, 2014 at 17:33
• but is that enough? i must show that the set I mentioned is the smallest convex set containing C. And I assume A i B are ok? Commented Oct 6, 2014 at 17:40
• $\operatorname{Conv}(A)$ isn’t just the boundary: it’s the whole triangle. For instance, $$\frac13(0,0)+\frac13(0,1)+\frac13(1,0)=\left(\frac13,\frac13\right)$$ is in the convex hull. Commented Oct 6, 2014 at 17:40
• Ohh. My bad. Thanks. Commented Oct 6, 2014 at 17:42

## 1 Answer

In the following, we shall work with the following definition of the convex hull of a set $B$ in a vector space $V$:

Def:

Let $V$ be a vector space, and let $B \subseteq V$. $P \subseteq V$ is called the convex hull of $B$ iff $P$ is a convex set such that

• $B \subseteq P$
• for all convex sets $Q \subseteq V$ such that $B \subseteq Q$ we have $P \subseteq Q$

OK, so now let's start with the formal proofs.

First convex hull

We prove that the set

$$A_1 := \{(x, y) \in \mathbb R^2 \big| x, y \ge 0 \wedge |x| + |y| \le 1\}$$

is the convex hull of the set $\{(0, 0), (0, 1), (1, 0)\}$. So first, we note that $\{(0, 0), (0, 1), (1, 0)\} \subseteq A_1$. Second, we note that $A_1$ is convex, since for any $(x, y), (z, w) \in A_1$ and $\lambda \in [0, 1]$, we have

$$\lambda x + (1 - \lambda) z, \lambda y + (1 - \lambda) w \ge 0$$ and

$$|\lambda x + (1 - \lambda) z| + |\lambda y + (1 - \lambda) w| \le \lambda(|x| + |y|) + (1 - \lambda) (|z| + |w|) \le 1$$

Third, let $Q$ be any convex set containing $\{(0, 0), (0, 1), (1, 0)\}$. We show that every element of $A_1$ is in $Q$. Let thus $(x, y) \in A_1$ be arbitrary. Then we have $|x| + |y| \le 1$ and $|x| = x$, $|y| = y$. Therefore, the two elements $(0, |x| + |y|)$ and $(|x| + |y|, 0)$ are also contained in $Q$ as a convex combination of $(0, 1)$ and $(0,0)$ or $(0, 1)$ and $(0,0)$ respectively. Now either $x = y = 0$ and thus from $\{(0, 0), (0, 1), (1, 0)\} \subset Q$ automatically follows $(x, y) \in Q$ or we choose $\lambda = \frac{x}{x + y} \in [0, 1]$ and find

\begin{align} \lambda(|x| + |y|) & = x \\ (1 - \lambda)(|x| + |y|) & = y \\ \end{align}

, which is why $(x, y) \in Q$, as $Q$ was supposed to be convex. $\Box$

Second convex hull

Because $\mathbb Q \subset \mathbb R$, it follows that $\mathbb Q^2 \subset \mathbb R^2$. Further, since $\mathbb R^2$ is a vector space, it is convex. Now let $Q$ be an arbitrary convex superset of $\mathbb Q^2$. We show that $\mathbb R^2 \subseteq Q$. Let $(x, y) \in \mathbb R^2$. Of course, the four elements $(\lfloor x \rfloor, \lfloor y \rfloor)$, $(\lfloor x \rfloor + 2, \lfloor y \rfloor)$ and $(\lfloor x \rfloor, \lfloor y \rfloor + 2)$ are contained in $\mathbb Q^2$ (and thus in $Q$). Since $0 \le x - \lfloor x \rfloor + y - \lfloor y \rfloor < 2$, if we choose $\lambda_1 := \frac{x - \lfloor x \rfloor + y - \lfloor y \rfloor}{2}$, then $\lambda_1 \in [0, 1]$. Further,

\begin{align} \lambda_1 (\lfloor x \rfloor + 2, \lfloor y \rfloor) + (1 - \lambda_1) (\lfloor x \rfloor, \lfloor y \rfloor) & = (x + y - \lfloor y \rfloor, \lfloor y \rfloor) \\ \lambda_1 (\lfloor x \rfloor, \lfloor y \rfloor + 2) + (1 - \lambda_1) (\lfloor x \rfloor, \lfloor y \rfloor) & = (\lfloor x \rfloor, y + x - \lfloor x \rfloor) \\ \end{align}

Now either both $\lfloor x \rfloor = x$ and $\lfloor y \rfloor = y$ and thus $(x, y) \in \mathbb Q^2 \subseteq Q$, or we now choose $\lambda_2 := \frac{x - \lfloor x \rfloor}{x - \lfloor x \rfloor + y - \lfloor y \rfloor}$. Then

$$\lambda_2 (x + y - \lfloor y \rfloor, \lfloor y \rfloor) + (1 - \lambda_2) (\lfloor x \rfloor, y + x - \lfloor x \rfloor) = (x, y)$$

As $Q$ was supposed to be convex, all these elements, including the last one, are in $Q$. This shows that $\mathbb R^2 \subseteq Q$ and thus $\mathbb R^2$ is the convex hull of $\mathbb Q^2$. $\Box$

Third convex hull

We show that

$$A_2 := \{(x, y) \in \mathbb R^2 \big| x, y > 0 \wedge y \le \sqrt{x} \} \cup \{(0, 0)\}$$

is the convex hull of the set you denoted by $C$. It is easy to see that $C \subset A_2$. Further, $A_2$ is convex: Let $(x, y), (z, w) \in A_2$, $\lambda \in [0, 1]$. For $(x, y) = (z, w)$, clearly $\lambda (x, y) + (1 - \lambda)(z, w) = (x, y) \in A_2$. Otherwise $\lambda x + (1 - \lambda) z > 0$ and $0 < \lambda y + (1 - \lambda) w \le \lambda \sqrt{y} + (1 - \lambda) \sqrt{w} \le \sqrt{\lambda y + (1 - \lambda) w}$, where in the last $\le$ we used that $x \mapsto \sqrt{x}$ is a concave function. Thus, $\lambda (x, y) + (1 - \lambda)(z, w) \in A_2$.

Third, let now $Q$ be any convex set such that $C \subset Q$. We show that $A_2 \subseteq Q$. Let $(x, y) \in A_2$ be arbitrary. The first possibility is $(x, y) = (0, 0)$. In this case, $(x, y) \in C \subset Q$ and thus $(x, y) \in Q$. The second possibility is $(x, y) \neq (0, 0)$. In this case, the point $\left( \frac{x^2}{y^2}, \frac{x}{y} \right)$ is well-defined and contained in $C$. Further, of course, $(0, 0) \in C$. Since $Q$ contains $C$, of course also $(0, 0), \left( \frac{x^2}{y^2}, \frac{x}{y} \right) \in Q$. We choose now $\lambda := \frac{y^2}{x}$, and observe that since $(x, y) \in A_2$, $\lambda \in [0, 1]$. Then $\lambda \left( \frac{x^2}{y^2}, \frac{x}{y} \right) + (1 - \lambda) (0, 0) = (x, y) \in Q$ due to convexity of $Q$. Thus $A_2 \subseteq Q$ and $A_2$ is the convex hull of $C$. $\Box$

General recipe

• Try to visualize the convex hull in your inner eye and guess it.
• Show that your guess contains the set of which you wanted to find the convex hull.
• Prove that your guess is convex.
• Prove that any convex set containing the set will include your guess (here you will find any imprecisions your guess contained).
• Thanks a lot again. But how would the proof of 3rd case change if $C=\{(x,\sqrt{x})\in \mathbb{R}^2:x>0\}$ instead of $C=\{(x,\sqrt{x})\in \mathbb{R}^2:x\ge0\}$ Commented Nov 5, 2014 at 22:00
• In this case, the convex hull would be given by Commented Nov 7, 2014 at 9:57
• In this case, the convex hull would be given by $A_3 := \{(x, y) \in \mathbb R^2 \big| x, y > 0 \wedge y \le \sqrt{x}\}$, i. e. without the $(0, 0)$. It's easy to show that this set is convex (in fact I'm noticing right now that this is what I proved above; when I had written the answer I forgot to consider the case $(x, y) = (0, 0)$). In order to show that it's the smallest convex set, you first pick an $x$ s. t. your point $(z, w)$ in $A_3$ has a second coordinate larger than $\sqrt{x}$. In this case, it should be possible to draw a line through $(z, w)$ and $(x, \sqrt{x})$. Commented Nov 7, 2014 at 10:04
• Then you find the second intersection of this line with the graph, let's call it $(y, \sqrt{y})$. The respective $\lambda$ you find by solving $\lambda (x, \sqrt{x}) + (1 - \lambda) (y, \sqrt{y}) = (z, w)$. Commented Nov 7, 2014 at 10:06
• Sometimes I wish I were one... Commented Nov 7, 2014 at 22:58