# Intersection of 2 $p$-simplices is a finite union of some $p$-simplices

I'm looking for a non-painful proof of this assertion.

A p-simplex is defined as the set of all sums $\sum_{i=0}^p t_i x_i$ with $0\leq t_i\leq 1$, $\sum_{i=0}^p t_i=1$ for a geometrically independent set of points $x_i\in \mathbb{R}^{n}$ for $n\geq p-1$.

Additionally, is it possible to choose the finely many simplices so that each two of them share no interior points?

-
I guess it should follow from the theorem that asserts that a compact convex set (in some finite dimensional real vector space $V$) is equal to the convex envelope of its extremal points (I think that's Helley's theorem), and Caratheodory's theorem that tells us one only ever needs to consider convex combinations of $\dim~V+1$ points. One would then only need to prove that there are a finite amount of extremal points. Maybe the finiteness of the extremal points follows from the fact that this intersection can be caracterised as the intersection of a finite number of closed half spaces? –  Olivier Bégassat Jul 24 '12 at 21:04
You could probably show finiteness by recurrence on $p$. –  Olivier Bégassat Jul 24 '12 at 21:06
What would constitute a "painful proof" of this to you? –  Olivier Bégassat Jul 24 '12 at 21:44
I have next to no knowledge of convex geometry, so I was somewhat hoping for an elegant elementary proof. But I like the systematic approach you suggested as well. Now I edited the question to an interesting more general one. (I don't know if it is much more difficult to prove.) –  user35359 Jul 25 '12 at 19:49
I think the existence of such a decomposition will be easy (some maximality argument will do), but it may be hard to find one from the raw data. –  Olivier Bégassat Jul 25 '12 at 20:08

Let $s_1,\dots,s_p$ and $t_1,\dots,t_p$ be two sets of affinely independent vectors in $\mathbb R^{p-1}$, and $\sigma$ and $\tau$ their convex envelopes: $$\sigma=\lbrace \sum_1^px_i s_i|x_1,\dots,x_p\geq 0,~x_1+\dots+x_p=1\rbrace=conv(s_1,\dots,s_p)\\ \tau=\lbrace \sum_1^px_i t_i|x_1,\dots,x_p\geq 0,~x_1+\dots+x_p=1\rbrace=conv(t_1,\dots,t_p).$$ For any $1\leq i\leq p$, let $\sigma_i=conv(s_1,\dots,s_{i-1},s_{i+1},\dots,s_p)$ be the $i^{th}$ face of $\sigma$, and similarly for $\tau$. For a non-empty convex set $C$, define $\mathrm{Ext}(C)=$ the set of its extremal points i.e. the set of points in $C$ that aren't midpoints of proper segments contained in $C$.

A famous theorem asserts that for compact convex sets $K\subset\mathbb R^{p-1}$, $$K=\overline{conv}(\mathrm{Ext}(K)),$$ that is, $K$ coincides with the closed convex envelope of its extremal points.

We'll show that $$\mathrm{Ext}(\sigma\cap\tau)\subset\lbrace s_1,\dots,s_p,t_1,\dots,t_p\rbrace\cup\bigcup_{1\leq i,j\leq p}\mathrm{Ext}(\sigma_i\cap\tau_j)~~~~(*)$$ Since for $p=1$, the number of extremal points of a compact convex set is $1$ or $2$, by induction on the dimension $p$, the set of extremal points of an intersection of two $p$-simplices is finite.

So let's prove $(*)$. First of all, it is clear that if $x\in C\subset C'$ is an extremal point of $C'$, then it is an extremal point of $C$ aswell. So in order to prove the assertion, we only need to prove that any extremal point of $\sigma\cap\tau$ that is not a vertex of $\sigma$ or $\tau$ is contained in some $\sigma_i$ and some $\tau_j$. This is indeed true, for otherwise, such an extremal point would belong to (for instance) $\sigma\setminus\cup_1^p\sigma_i=\mathrm{Interior}~\sigma$ and to $\tau\setminus\lbrace t_1,\dots,t_p\rbrace=\tau\setminus\mathrm{Ext}(\tau)$, so it could be represented as a mid point of a proper segment $I$ included in $\tau$, and thus as a midpoint of a proper segment (actually a subsegment of $I$) included in $\sigma\cap\tau$ because $\sigma$ contains an open ball centered around that point, which contradicts the extremality of that point in $\sigma\cap\tau$. Thus every extremal point of $\sigma\cap\tau$ that is not a vertex of either $\sigma$ or $\tau$ belongs to an intersection of two faces $\sigma_i\cap\tau_j$, and by what precedes is an extremal point of that convex set.

So by induction on $p$, the set of extremal points of the intersection of two $p$-simplices is finite, and since the convex envelope of a compact set is compact (corollary to Caratheodory's theorem), we have $$\sigma\cap\tau=\overline{conv}(\mathrm{Ext}(\sigma\cap\tau))=\overline{conv}(\mathrm{finite~set})=conv(\mathrm{finite~set})\\ =\bigcup p\mathrm{-simplices~built~from~that~finite~set}$$ The last equality uses Carathedory's theorem, according to which, for any nonempty subset $S\subset\mathbb R^{p-1}$, $$conv(S)=\lbrace \sum_1^pt_is_i|s_1,,\dots,s_p\in S\rbrace.$$ This concludes the proof that the intersection of two $p$ simplices is a finite union of $p$-simplices.

-
Did you find this answer useful? Do you need clarification with anything? I don't think you can avoid using the standard machinery of convex sets, are you familiar with the theorems I cite? –  Olivier Bégassat Jul 25 '12 at 3:12
Thank you for your answer. It was all very understanable. I will have a look at a proof for the theorem you cited, it doesn't seem that difficult. –  user35359 Jul 25 '12 at 19:51
Here are some relevant links [Caraotheodory's Theorem][1] and the [Krein-Milman Theorem][2]. [1]: en.wikipedia.org/wiki/… [2]: en.wikipedia.org/wiki/Krein%E2%80%93Milman_theorem –  Olivier Bégassat Jul 25 '12 at 20:00