作者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/m.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