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?

  • $\begingroup$ 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. $\endgroup$
    – 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)<n$. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.