Convex hulls of a set and its subsets

Question

Suppose that $P$ is a set of $k>3$ points in $\mathbb{R}^2$. Let $\mathrm{Conv}(P)$ be the convex hull of $P$.

I think that the following claim is true (I know how to prove it geometrically) :

$\textbf{Claim}$: For any $p \in \mathrm{Int}(\mathrm{Conv}(P))$ there exist at least two distinct subsets $P',P''\subset P$ with 3 elements each, such that $p$ is in the convex hull of $P'$ and of $P''$ (i.e. $p \in \mathrm{Conv}(P')$ and $p \in \mathrm{Conv}(P'')$).

By "distinct subsets" I mean subsets that differ in at least one element.

I believe that this result is well-known. My questions are:

1. What is the classic reference to this result? Is it a direct implication of another well-known result?
2. Is this result generalizable? For example, is the claim still true if $P$ is a set with more than $n+1$ elements in $\mathbb{R}^n$ and $3$ in the claim is replaced with $n+1$?

Thanks.

Answer 1

I think your result follows from known properties of simplicial depth. The simplicial depth of a query point q with respect to a point set P is the number of simplices with vertices of P that contain q. (There are the different options of allowing q to be on the boundary or requiring it to be in the interior, but if you assume that the union of P and q is in general position, meaning no d+1 points are on a common hyperplane, where d is the dimension, thus does not matter).

It is now known that the simplicial depth of q is >0 whenever q is in the convex hull of P, and, in fact the depth can be bounded from below by n-d, where n is the number of points in P and d is the dimension. In particular, for d=2 and n>3, this is exactly your result.

There are several places, where a proof of thus can be found, here is a link to some nice lecture notes about bounds for simplicial depth.

Answer 2

Here is an elementary approach. Convex analysis has results that are intuitively obvious but tedious to prove.

Let $C=\operatorname{co}P$ and $p \in C$. (No need to be in the interior.)

From Carathéodory's theorem there are $m \le 3$ ($= \dim \mathbb{R}^2+1$) affinely independent points $x_k \in P$ such that $p = \sum_{k=1}^m \mu_k x_k$ with $\sum_{k=1}^m \mu_k = 1$ and $\mu_k > 0$.

If $m=1$ then pick distinct $x_2,x_3,x_4 \in P \setminus \{x_1 \}$ and set $P'= \{x_1, x_2,x_3 \}$, $P''= \{x_1, x_2,x_4 \}$.

If $m=2$ then pick distinct $x_3,x_4 \in P \setminus \{x_1, x_2 \}$ and set $P'= \{x_1, x_2,x_3 \}$, $P''= \{x_1, x_2,x_4 \}$.

So we can assume $m = 3$. Choose any point $x_4 \in P \setminus \{x_1,x_2,x_3 \}$.

For $x \in \mathbb{R}^2$ let $\bar{x} = \binom{1}{x}$ and define $\bar{X} = \begin{bmatrix} \bar{x}_1 & \bar{x}_2 & \bar{x}_3 & \bar{x}_4\end{bmatrix}$. Since $x_1,x_2,x_3$ are affinely independent, the points $\bar{x}_1, \bar{x}_2, \bar{x}_3 $ are linearly independent and so $\ker \bar{X}$ has dimension one. Let $n \in \ker \bar{X}$ such that $n_4 >0$.

Note that we can write $\bar{p} = \bar{X} \mu $ with $\mu_4 = 0$.

Since $\sum_{k=1}^4 n_k = 0$ we see that there is at least one $k$ such that $n_k < 0$. Let $t^* = \min_{n_k < 0} (- { \mu_k \over n_k }) $. Let $\mu^* = \mu+t^* n$ and note that $\sum_{k=1}^4 (\mu_k + t^*n_k) = 0$ and $\mu_k + t^*n_k \ge 0$ and there is some $k \in \{1,2,3\}$ such that $\mu_k + t^*n_k = 0$. Now let $P'= \{x_1,x_2,x_3\}$ and $P''= \{x_1,x_2,x_4\}$.

The result generalises to $\mathbb{R}^n$.