# How can I solve the problem of convex hull

Let $$\DeclareMathOperator{\Conv}{\mathrm{Conv}} C=\Conv(v_1,v_2,...,v_m)$$, where $$v_1,v_2,...,v_m$$ are $$m$$ points in $$\mathbb{R}^n$$ and 'Conv' means the convex hull. Please prove
$$\partial C=\cup_{D\in S}\Conv(v_i:i\in D)$$ where

• $$\partial C$$ denotes the boundary of $$C$$ and
• $$S$$ is defined as the set $$S=\left\{D\subset\{1,2,\dots,m\} : \exists d\in\mathbb{R}^n \text{ such that } \begin{split} \langle v_i,d\rangle=1 &\;\forall i\in D \\ \langle v_i,d\rangle<1 &\:\forall i \notin D \end{split}\right\}$$

I have tried to prove it by using the fact that the boundary of $$C$$ is the union of all edges. However I cannot give an explicit proof. Can you give me some concrete hints and references?

• This is false if the origin isn’t in $C$. For one dir, you can show $v_i+\epsilon d$ isn’t in $C$. For the other, every point in $C$ is a linear combination of the vertices, so maybe see what happens when you tweak those coefficients.
– Eric
Jul 10 '21 at 16:06

As Eric said, the statement should assume that origin is in the interior of $$C$$.
Hint: Consider that, there is $$d$$ such that $$\langle d, v_i \rangle =1$$ for all $$v_i\in D$$ iff (when thinking elements of $$D$$ as points instead of vectors) $$D\subset H$$ for some $$H$$, such that $$H$$ is a hyperplane not through origin and $$dim(H). When this condition is met, defining $$T$$ to be the hyperplane orthogonal to $$H$$ and through origin, $$d$$ is a vector on $$T$$ (the hyperplane orthogonal to $$H$$ and through origin) such that $$\langle d, proj_{T}H\rangle=1$$.
Partial solution: Because the convex object $$C$$ contains the origin and it is suppsed that $$H$$ does not, the condition that $$\partial conv(D)\subset\partial C$$ is equivalent to $$|proj_{T}(D)|>|proj_{T}(v_j)|$$ for every $$v_j$$ not included in $$D$$. Divide the inequality by $$|proj_{T}(D)|$$ on both sides and the latter condition recovers definition $$\langle d, v_j\rangle<1$$ for $$v_j\notin D$$.
I think of the last paragraph as a criterion of deciding whether $$D$$ contains all the element (so the equality is straight) of the "most outward" hyperplane in any direction/dimension.