1
$\begingroup$

That is, if $P$ is a finite set, and $C$ is the set of points in $P$ which lie on the boundary of the convex hull of $P$, then is $P$ contained in the convex hull of $C$?

It seems true intuitively. In my problem, it is okay to assume that $P\subset\mathbb{R}^d$. Any help would be greatly appreciated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

$\newcommand\conv{\operatorname{conv}}\newcommand\ext{\operatorname{ext}}\newcommand\p{\partial}$The answer is yes. Indeed, let $K:=\conv P$ (the convex hull of $P$), let $\p K$ be the boundary of $K$, and let $\ext K$ be the set of all extreme points of $K$. Then $K=\conv\ext K$, $\ext K=P\cap\ext K$, $\ext K\subseteq\p K$, and $P\cap\p K=C$. So, $$P\subseteq\conv P=K=\conv\ext K \\ =\conv(P\cap\ext K) \subseteq\conv(P\cap\p K)=\conv C.\quad\Box$$

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you very much. Is there any reference (books, lecture notes, or books) where I can study proofs of $K=\textrm{conv } \textrm{ext } K$, $\textrm{ext } K = P\cap\textrm{ext } K$, and $\textrm{ext }K\subseteq\partial K$? $\endgroup$
    – one-day-at-a-time
    Commented Nov 6, 2023 at 8:48
  • $\begingroup$ I think the first one is from the Krein-Milman theorem. $\endgroup$
    – one-day-at-a-time
    Commented Nov 6, 2023 at 8:58
  • $\begingroup$ It seems $C$ is also referred to as vertices. Since I am not familiar with this field, I am looking for a guide. $\endgroup$
    – one-day-at-a-time
    Commented Nov 6, 2023 at 9:18
  • $\begingroup$ @one-day-at-a-time : Since your set $P$ is finite, without loss of generality it is a subset of $\mathbb R^d$ for some $d$. The best book on this topic is Convex Analysis by R. Tyrrell Rockafellar. I will refer to the 1970 edition of this book. $K=\conv\ext K$ indeed follows from the Krein--Milman theorem, or from Corollary 18.5.1 of Rockafellar's book. $\ext K=P\cap\ext K$ or, equivalently, $\ext K\subseteq P$ follows from Corollary 18.3.1 of the same book. $\ext K\subseteq\partial K$ is an easy exercise, following immediately from the definitions of $\ext K$ and $\partial K$. $\endgroup$
    – Iosif Pinelis
    Commented Nov 6, 2023 at 15:31
  • $\begingroup$ Thank you very much for your kind guide. :D $\endgroup$
    – one-day-at-a-time
    Commented Nov 6, 2023 at 16:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .