證明convex hull的另一種表示法是相等的

看板Math作者 (jr80939393)時間3年前 (2020/10/20 12:08), 編輯推噓0(0推 0噓 49→)
留言49則, 3人參與, 3年前最新討論串1/1
如圖片，我想證明一個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://www.ptt.cc/bbs/Math/M.1603166889.A.395.html
→
10/20 13:33, 3年前 , 1F
induction on p, p是1時顯然 對於一般p 先考慮Q1,Q2
10/20 13:33, 1F
→
10/20 13:34, 3年前 , 2F
Q3,...,Qp,Q{p+1},Q{p+2}所形成的convex hull
10/20 13:34, 2F
→
10/20 13:37, 3年前 , 3F
若其中Q1,Q2,...,Q{p+1}的convex hull C'是p-1維的
10/20 13:37, 3F
→
10/20 13:39, 3年前 , 4F
這裡要注意到的是對所有p在C中 p都會在Q{p+2}和p'的
10/20 13:39, 4F
→
10/20 13:42, 3年前 , 5F
線段上 for some p' in C' (觀察p=ΣciQi就知道了)
10/20 13:42, 5F
→
10/20 13:44, 3年前 , 6F
by induction hypothesis 這個case ok
10/20 13:44, 6F
→
10/20 13:46, 3年前 , 7F
接下來假設對任意p+1個點 都不會落在p-1維的
10/20 13:46, 7F
→
10/20 13:47, 3年前 , 8F
hyperplane上 則{Q1,...,Q{p-1},Qp},
10/20 13:47, 8F
→
10/20 13:49, 3年前 , 9F
{Q1,...,Q{p-1},Q{p+1}}, {Q1,...,Q{p-1},Q{p+2}}會
10/20 13:49, 9F
→
10/20 13:51, 3年前 , 10F
形成三個不同的hyperplane 故至少其中一個hyperplan
10/20 13:51, 10F
→
10/20 13:54, 3年前 , 11F
會分隔剩餘兩點(這裡需要用線代證明 有些複雜) 就假
10/20 13:54, 11F
→
10/20 13:55, 3年前 , 12F
設Q{p+1}和Q{p+2}在{Q1,...,Q{p-1},Qp}所形成的平面
10/20 13:55, 12F
→
10/20 13:58, 3年前 , 13F
異側 則存在0<=d1,d2<=1使得d1+d2=1,d1Q{p+1}+d2Q2
10/20 13:58, 13F
→
10/20 14:00, 3年前 , 14F
平面上 令C'為Q1,...,Q{p-1},Qp,d1Q{p+1}+d2Q{p+2}
10/20 14:00, 14F
→
10/20 14:01, 3年前 , 15F
所形成的convex hull 則可以證明對所有p在C中 都存
10/20 14:01, 15F
→
10/20 14:03, 3年前 , 16F
在p'在C'中使得 p要嘛在p'Q{p+1}上 要嘛在p'Q{p+2}
10/20 14:03, 16F
→
10/20 14:04, 3年前 , 17F
(同樣討論p=ΣciQi就可以了 不過情況更複雜)
10/20 14:04, 17F
→
10/20 14:05, 3年前 , 18F
by induction hypothesis 這個case就結束了
10/20 14:05, 18F
→
10/20 14:07, 3年前 , 19F
現在考慮p=c1Q1+c2Q2+...+cpQp+c{p+1}Q{p+1}+
10/20 14:07, 19F
→
10/20 14:09, 3年前 , 20F
c{p+2}Q{p+2}+dQ{p+3}=(1-d)*[(c1/(1-d))*Q1+...+
10/20 14:09, 20F
→
10/20 14:11, 3年前 , 21F
(c{p+2}/(1-d))*Q{p+2}]+dQ{p+3} 其中(c1/(1-d))*Q1
10/20 14:11, 21F
→
10/20 14:13, 3年前 , 22F
+...+(c{p+2}/(1-d))*Q{p+2}可以縮減成p+1個 所以整
10/20 14:13, 22F
→
10/20 14:14, 3年前 , 23F
個式子可以再縮減成p+2項 然後再縮一次即可
10/20 14:14, 23F
→
10/20 14:16, 3年前 , 24F
很多細節沒寫 覺得哪有問題再補上 抱歉
10/20 14:16, 24F
→
10/20 15:04, 3年前 , 25F
(Lem) dim = p, given |C| >= p+2
10/20 15:04, 25F
→
10/20 15:04, 3年前 , 26F
There exists a hyperplane E=0 (of dim p-1)
10/20 15:04, 26F
→
10/20 15:04, 3年前 , 27F
(1) Either every pt of C is on E=0, or
10/20 15:04, 27F
→
10/20 15:04, 3年前 , 28F
(2) E contains at least p pts of C
10/20 15:04, 28F
→
10/20 15:04, 3年前 , 29F
and both (C cap E>0) and (C cap E<0)
10/20 15:04, 29F
→
10/20 15:04, 3年前 , 30F
is nonempty
10/20 15:04, 30F
→
10/20 15:04, 3年前 , 31F
如果這個 Lemma 是對的話
10/20 15:04, 31F
→
10/20 15:05, 3年前 , 32F
一個簡單的 strong induction 就能做完
10/20 15:05, 32F
→
10/20 15:05, 3年前 , 33F
反正切兩半就好
10/20 15:05, 33F
→
10/20 15:05, 3年前 , 34F
但是這個 Lemma 我不會證 我也不保證是對的XD
10/20 15:05, 34F
→
10/20 17:05, 3年前 , 35F
謝謝h大每次用心的回覆，大致上理解！
10/20 17:05, 35F
→
10/20 17:06, 3年前 , 36F
謝謝T大提供的lemma，我會想想看的
10/20 17:06, 36F
→
10/20 18:09, 3年前 , 37F
T大的定理是對的 基本上[13:37]和[13:51]的論證 不
10/20 18:09, 37F
→
10/20 18:10, 3年前 , 38F
過接下來的induction會有點坎 例如考慮三角形ABC及
10/20 18:10, 38F
→
10/20 18:14, 3年前 , 39F
其內部一點D 令E為AD連線 接著會有點小困難 冏
10/20 18:14, 39F
→
10/20 18:42, 3年前 , 40F
不過如果能證所有的點都可以由邊界的點組合出來的話
10/20 18:42, 40F
→
10/20 18:43, 3年前 , 41F
應該就能順利搭配T大Lemma做inducition
10/20 18:43, 41F
→
10/20 19:45, 3年前 , 42F
好的 謝謝h大
10/20 19:45, 42F
→
10/20 21:31, 3年前 , 43F
嗯 這樣我的證明是錯的ow o
10/20 21:31, 43F
→
10/20 21:31, 3年前 , 44F
要多一個前提是 every point of C
10/20 21:31, 44F
→
10/20 21:31, 3年前 , 45F
is on the boundary of convex hull
10/20 21:31, 45F
→
10/20 21:32, 3年前 , 46F
不過這可以簡單地用砍掉所有內部點得到
10/20 21:32, 46F
→
10/20 21:35, 3年前 , 47F
好像還是錯
10/20 21:35, 47F
→
10/20 21:37, 3年前 , 48F
必須要 every points of C are vertex
10/20 21:37, 48F
→
10/20 21:37, 3年前 , 49F
怎麼感覺越來越麻煩了=A= 算了落跑XD
10/20 21:37, 49F
‣ 更多 jr80939393 的文章
文章代碼(AID): #1VZcAfEL (Math)