|
|
本帖最后由 hbghlyj 于 2023-5-6 23:26 编辑 CSDN
陈述:在$\Bbb R^d$中对于任意$d+2$个点,他们可以被划分为了两个不相交集合$A_1,A_2$,他们的凸包conv($A_1$),conv($A_2$)交集不为空.
例子:平面上四个点,若凸包为凸四边形,取$A_1,A_2$为它的两条对角线的端点;若凸包为三角形,取$A_1$为这个三角形的顶点,$A_2$为第四点;若凸包为线段,取$A_1$为这个线段的端点,$A_2$为其余的两点.
证明:回顾一下之前学的.之前简单学过凸集的概念,这里需要用到:对于一个点集$P=\{p_1,p_2,⋯,p_n\}$,假设它们构成的凸集是$\mathcal{P}=\operatorname{conv}(P)$.那么,对于任何一个$p\in\mathcal P$存在正数$t_i$满足$\sum_{i=1}^nt_i=1$以及$p=\sum_{i=1}^nt_ip_i$
证明的第一步是,找到这样的一组$\alpha_i$满足:$\sum_{i=1}^{d+2}t_2\alpha_ip_i=0$以及$\sum_{i=1}^{d+2}\alpha_i=0$以及$\alpha_i$不全部为0.
注意到本身是$d$维空间的,所以$p_2-p_1,p_3-p_1,p_4-p_1,⋯,p_{d+2}-p_1$这$d+1$个点线性相关,即存在$\beta_i$使得$$p_2-p_1=\sum_{i=3}^{d+2}\beta_i(p_i-p_1)$$整理得$$(\beta_3+\beta_4+⋯+\beta_{d+2}-1)p_1+p_2-\beta_3p_3-⋯-\beta_{d+2}p_{d+2}=0$$我们找到了满足条件的一组:$\sum_{i=1}^{d+2}\alpha_ip_i=0$以及$\sum_{i=1}^{d+2}\alpha_i=0$以及$\alpha_i$不全部为0
将$\alpha_i$大于0的分为一组$P_1$且集合求和为$S_1$,$\alpha_i$小于0的分为一组$P_2$,集合求和为$S_2$并且有:$S_1=-S_2$(因为$\sum_{i=1}^{d+2}\alpha_i=0$)
考察:$x ={\sum_{i\in P_1}\alpha_i p_i\over S_1}$
注意这一组条件显然满足我们的凸集内部的符号定义:$\sum_{i=1}^nt_i=1$以及$p=\sum_{i=1}^nt_ip_i$,这里的$t_i$就是$\alpha_i\over S_1$.
设$V_1$为$P_1$系数对应的点集,$V_2$为$P_2$系数对应的点集,所以$x\in\operatorname{conv}(V_1)$.
再次观察式子:$x={\sum_{i\in P_1}\alpha_i p_i\over S_1}={-\sum_{i\in P_2}\alpha_i p_i\over-S_2}={\sum_{i\in P_2}\alpha_i p_i\over S_2}$所以$x\in\operatorname{conv}(V_2)$.
所以$\operatorname{conv}(V_2)$与$\operatorname{conv}(V_1)$交集不为空. |
|
