Radonovo lemma

Radonovo lemma je tvrzení v kombinatorické geometrii, které říká, že dostatečně velkou množinu bodů v prostoru lze rozdělit na dvě části tak, aby se jejich konvexní obaly protínaly. Toto lemma se používá například v důkazu Hellyho věty a je elementárním výsledkem kombinatorické geometrie. Johann Radon je formuloval v roce 1921.

Znění lemmatu

Nechť $X=\{x_1,x_2,\dots x_n\}\subset {ℝ}^d$ a $n\ge d+2$. Potom existuje rozdělení $A,B\subset X:A\cap B=\mathrm{\varnothing }\wedge A\cup B=X$ takové, že $\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(A)\cap \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(B)\ne \mathrm{\varnothing }$.

Důkaz

Nechť $X$ je množina bodů ze znění lemmatu. $n\ge d+2$, tedy $X$ je afinně závislá množina. Tedy existují ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n\in ℝ,\sum _{i=1}^n{\alpha }_i=0$ takové, že $\sum _{i=1}^n{\alpha }_i{x}_i=0$ je netriviální kombinace.

Definujme $A=\{x_i|{\alpha }_i>0\},B=X\setminus A$ a hodnotu $S=\sum _{x_i\in A}{\alpha }_i\ne 0$. Potom také platí $-S=\sum _{x_i\in B}{\alpha }_i$, protože $\sum _{i=1}^n{\alpha }_i=0$.

Potom bod $z=\sum _{x_i\in A}\frac{{\alpha }_i}{S}{x}_i$ je konvexní kombinací bodů v $A$, protože $\mathrm{\forall }i\in J_A=\{j\in \{1,2,\dots ,n\}|x_j\in A\}:\frac{{\alpha }_i}{S}\ge 0$ a platí $\sum _{i\in J_A}\frac{{\alpha }_i}{S}=\frac{1}{S}\sum _{i\in J_A}{\alpha }_i=\frac{1}{S}S=1$.

Zároveň ale $z=\sum _{x_i\in B}\frac{-{\alpha }_i}{S}{x}_i$, což je opět konvexní kombinace bodů v $B$ z analogických důvodů. Tedy $z$ je v konvexním obalu $A$ i $B$ a proto $\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(A)\cap \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(B)\supseteq \{z\}\ne \mathrm{\varnothing }$. Šablona:Autoritní data