Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
show 1 more comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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