Show that convex hull can be represented as an intersection of half-spaces

Question

Yesterday I've stuck with the following problem:
Suppose that $a_0, a_1, ..., a_n$ are affine independent points of $n$-dimensional affine space.
$H_i$ is the hyperplane that passes through all these points except for $i$ ($i=0, 1, dots, n$).
$H_i^+$ is the half-space bounded by $H_i$ that contains $a_i$. Show that
$$
text{conv} {a_0, a_1, dots, a_n} = bigcap_{i=0}^n H_i^+
$$
My attempt(s):
Firstly let's note that $H^+:=bigcap_{i=0}^n H_i^+$ is the convex set contains all points $a_0, a_1, ..., a_n$ (as an intersection of such sets).
Then I see two opportunities that can bring us to solution:

Let S be an arbitrary convex set that contains $a_0, a_1, ..., a_n$. We need to show that $H^+ subseteq S$
Show that $H^+={ sum_{i=0}^n mu_i a_i: sum_{i=0}^n mu_i=1 space text{and} space mu_i ge0, space i=0, 1, dots, n }$

If it helps, I'll describe my thoughts on both of these ways. But actually I didn't solve the problem.
Any ideas?
HINT from the TextBook: consider the barycentric coordinate system associated with $a_0, a_1, dots, a_n$

gpassante · Accepted Answer

Let $;g_i=0;$ be an equation of the hyperplane $H_i;$ $(i=0,1,ldots,n)$, that is
$$ g_i : E to Bbb R quad text{an affine function with}quad H_i=g_i^{-1}(0), $$
where $;E;$ is the affine (real) space in which we are working. The half-space $;H_i^+;$ is described by the inequality $;g_igeq0;$ or $;g_ileq0$, and we can assume, for simplicity, that it is of the form $;g_igeq0;$, changing the sign of $;g_i;$ if necessary. We have, for each $;i=0,1,ldots,n$:
$$ g_i(a_i)>0 qquad text{ and }qquad g_i(a_j)=0 text{$;;$ for$;;$}jneq i. tag{1}$$
Note that it cannot be $;g_i(a_i)=0;$ because otherwise it would be $;a_iin H_i$.
Now let $;xin H^+:=displaystyle bigcap_{i=0}^nH_i^+$. This implies that $;g_i(x)geq0, forall i$. With respect to the barycentric coordinate system associated with $(a_0,a_1,ldots,a_n)$, we can write
$$ x=sum_{j=0}^n lambda_ja_jqquadtext{with}quad sum_{j=0}^nlambda_j=1 $$
and therefore we only need to prove that all the $lambda's;$ are $;geq0;$. This follows from $(1)$:
$$ g_i(x) = g_ibig(sum_{j=0}^{n}lambda_ja_jbig) = sum_{j=0}^{n}lambda_jg_i(a_j) = lambda_ig_i(a_i) $$
and the conclusion follows from $;g_i(x)geq0;$ and $;g_i(a_i)>0$.

Show that convex hull can be represented as an intersection of half-spaces

One Answer

Add your own answers!

Ask a Question