作者jr80939393 (jr80939393)
看板Math
标题证明convex hull的另一种表示法是相等的
时间Tue Oct 20 12:08:07 2020
如图片，我想证明一个affine dimension为p的集合C(包含多於p+1个点) ，其convex hull一定可以表示为其任意p+1个点的convex hull联集。
用集合的包含性质或是数学归纳法(p+k个点可以表示成p+1个点的convex hull 联集)，都没办法把证明写的很完整，希望板上的高手给我一点提示，谢谢大家。
https://i.imgur.com/AJZQS8m.jpg
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.114.27.185 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1603166889.A.395.html
1F：→ hwanger : induction on p, p是1时显然 对於一般p 先考虑Q1,Q2 10/20 13:33
2F：→ hwanger : Q3,...,Qp,Q{p+1},Q{p+2}所形成的convex hull 10/20 13:34
3F：→ hwanger : 若其中Q1,Q2,...,Q{p+1}的convex hull C'是p-1维的 10/20 13:37
4F：→ hwanger : 这里要注意到的是对所有p在C中 p都会在Q{p+2}和p'的 10/20 13:39
5F：→ hwanger : 线段上 for some p' in C' (观察p=ΣciQi就知道了) 10/20 13:42
6F：→ hwanger : by induction hypothesis 这个case ok 10/20 13:44
7F：→ hwanger : 接下来假设对任意p+1个点 都不会落在p-1维的 10/20 13:46
8F：→ hwanger : hyperplane上 则{Q1,...,Q{p-1},Qp}, 10/20 13:47
9F：→ hwanger : {Q1,...,Q{p-1},Q{p+1}}, {Q1,...,Q{p-1},Q{p+2}}会 10/20 13:49
10F：→ hwanger : 形成三个不同的hyperplane 故至少其中一个hyperplan 10/20 13:51
11F：→ hwanger : 会分隔剩余两点(这里需要用线代证明 有些复杂) 就假 10/20 13:54
12F：→ hwanger : 设Q{p+1}和Q{p+2}在{Q1,...,Q{p-1},Qp}所形成的平面 10/20 13:55
13F：→ hwanger : 异侧 则存在0<=d1,d2<=1使得d1+d2=1,d1Q{p+1}+d2Q2 10/20 13:58
14F：→ hwanger : 平面上 令C'为Q1,...,Q{p-1},Qp,d1Q{p+1}+d2Q{p+2} 10/20 14:00
15F：→ hwanger : 所形成的convex hull 则可以证明对所有p在C中 都存 10/20 14:01
16F：→ hwanger : 在p'在C'中使得 p要嘛在p'Q{p+1}上 要嘛在p'Q{p+2} 10/20 14:03
17F：→ hwanger : (同样讨论p=ΣciQi就可以了 不过情况更复杂) 10/20 14:04
18F：→ hwanger : by induction hypothesis 这个case就结束了 10/20 14:05
19F：→ hwanger : 现在考虑p=c1Q1+c2Q2+...+cpQp+c{p+1}Q{p+1}+ 10/20 14:07
20F：→ hwanger : c{p+2}Q{p+2}+dQ{p+3}=(1-d)*[(c1/(1-d))*Q1+...+ 10/20 14:09
21F：→ hwanger : (c{p+2}/(1-d))*Q{p+2}]+dQ{p+3} 其中(c1/(1-d))*Q1 10/20 14:11
22F：→ hwanger : +...+(c{p+2}/(1-d))*Q{p+2}可以缩减成p+1个 所以整 10/20 14:13
23F：→ hwanger : 个式子可以再缩减成p+2项 然後再缩一次即可 10/20 14:14
24F：→ hwanger : 很多细节没写 觉得哪有问题再补上 抱歉 10/20 14:16
25F：→ TimcApple : (Lem) dim = p, given |C| >= p+2 10/20 15:04
26F：→ TimcApple : There exists a hyperplane E=0 (of dim p-1) 10/20 15:04
27F：→ TimcApple : (1) Either every pt of C is on E=0, or 10/20 15:04
28F：→ TimcApple : (2) E contains at least p pts of C 10/20 15:04
29F：→ TimcApple : and both (C cap E>0) and (C cap E<0) 10/20 15:04
30F：→ TimcApple : is nonempty 10/20 15:04
31F：→ TimcApple : 如果这个 Lemma 是对的话 10/20 15:04
32F：→ TimcApple : 一个简单的 strong induction 就能做完 10/20 15:05
33F：→ TimcApple : 反正切两半就好 10/20 15:05
34F：→ TimcApple : 但是这个 Lemma 我不会证 我也不保证是对的XD 10/20 15:05
35F：→ jr80939393 : 谢谢h大每次用心的回覆，大致上理解！ 10/20 17:05
36F：→ jr80939393 : 谢谢T大提供的lemma，我会想想看的 10/20 17:06
37F：→ hwanger : T大的定理是对的 基本上[13:37]和[13:51]的论证 不 10/20 18:09
38F：→ hwanger : 过接下来的induction会有点坎 例如考虑三角形ABC及 10/20 18:10
39F：→ hwanger : 其内部一点D 令E为AD连线 接着会有点小困难 冏 10/20 18:14
40F：→ hwanger : 不过如果能证所有的点都可以由边界的点组合出来的话 10/20 18:42
41F：→ hwanger : 应该就能顺利搭配T大Lemma做inducition 10/20 18:43
42F：→ jr80939393 : 好的 谢谢h大 10/20 19:45
43F：→ TimcApple : 嗯 这样我的证明是错的ow o 10/20 21:31
44F：→ TimcApple : 要多一个前提是 every point of C 10/20 21:31
45F：→ TimcApple : is on the boundary of convex hull 10/20 21:31
46F：→ TimcApple : 不过这可以简单地用砍掉所有内部点得到 10/20 21:32
47F：→ TimcApple : 好像还是错 10/20 21:35
48F：→ TimcApple : 必须要 every points of C are vertex 10/20 21:37
49F：→ TimcApple : 怎麽感觉越来越麻烦了=A= 算了落跑XD 10/20 21:37