Let $S_N \subseteq \mathbb{R}^n$ be the convex hull of a finite set of $N$ points in $\mathbb{R}^n$, i.e., $S_N := \mathrm{conv}(\{x_1, \ldots, x_N\})$, and let $V_N$ be the associated set of extreme points (vertices).
If one randomly adds an additional point (different from the previous ones), say $x_{N+1} \in \mathbb{R}^n$, can it happen that $V_{N+1} \subset V_{N} \cup \{x_{N+1}\}$, where $V_{N+1}$ is the set of vertices associated to $S_{N+1} := \mathrm{conv}(S_{N} \cup \{x_{N+1}\})$?
In summary, is it true that, in adding a new point, what can only happen is that either $V_{N+1} = V_{N}$, or $V_{N+1} = V_{N} \cup \{x_{N+1}\}$, and therefore the new point does not cut-off any vertex of $S_N$?
I know the answer is trivial, but I'm not able how to work this out.
Best Answer
If $x_N\in\text{conv}(V_n)$, then $V_{N+1}=V_N$.
If $x_N\notin\text{conv}(V_n)$, then $x_N$ may eliminate from $0$ to $N-n+1$ points (worst case when it reduces the hull to a simplex).