這段證明我覺得寫得很冗長 沒辦法很簡單的就知道我想要表達甚麼 而且課本上好像沒有這個演算法 只有稍微類似的演算法 希望有人可以幫我改的結構和邏輯好一點 附上圖之類的 ---------------------- 證明正確性的重點應該是 加入一個新的點之後 那個點會是新的convex hull的成員 而且那個點必須要連到哪個點 時間複雜度的難處是 刪除掉的點總共會花多少時間 找出加入的點必須連結到哪個點所花的時間 -------------------- 甚麼是convex hull? 對於點集合Q的最小凸多邊形P使Q的成員"不是在P的邊上就是在P的裡面" 則定義為CH(Q) 解決的方法 遞迴的演算法 做法 1 找出點集合Q中最左邊的點L 2 點p屬於{點集合Q中除了L的點} 3 依照線段(p,L)的斜率由小到大排序 4 形成點集合P={p2,p3,p4,.......,pn} 5 定義CHi(P)是點L和點p2到點pi形成的convex hull 6 令CH3(P)={L,P2,P3} 7 for i = 4 to n 8 let 點r1= L 9 let 點r2= 點r1沿著CHi邊順時針方向下一點 10 do theta=向量(r1-pi)和向量(rj-r2)的夾角 11 while theta>180度 12 let 點r1= r2 13 let 點r2= 點r1沿著CH(i-1)(P)邊順時針方向下一點 14 do theta=向量(r1-pi)和向量(rj-r2)的夾角 15 do CHi(P)= CH(i-1)(P)-(L沿著CHi的邊順時針走到r1所經過的所有點)+ pi 16 輸出CHn(P) 正確性 1.CH3(P)={L,P2,P3} 因為三個點才能形成凸包,所以CH3的成員一定會包含L,p2,p3 2.pi屬於CHi(P) 因為CHi(P)上的邊(L,pi)比邊(L,p'),p'是p2,p3,......,p(i-1)任何一點斜率都大 所以pi屬於CHi,否則其他的邊無法把pi包住 3.r2屬於CHi(P) 因為r2是第一個令theta<=180度的點 又因為CH(i-1)(P)是convex hull所以每個邊的夾角都<=180度 所以所有的點都會在線段(pi,r2)的同一邊 因此r2屬於CHi(P) 時間複雜度 line 1 花O(n) line 3 排序會花O(n*log(n)) line 6 O(1) line 7~15 每一次找CHi(P)需要加入一個點,花O(1) 刪去被原本是CH(i-1)(P)包住的點,因為每一點最多只能被刪去一次,所以是O(n) 找出r2要花的時間和刪去被原本是CH(i-1)(P)包住的點時間一樣,是O(n) 總和是O(n*log(n)) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 58.114.209.65 ※ 編輯: ajnightmare 來自: 58.114.209.65 (05/10 00:38) ※ 編輯: ajnightmare 來自: 58.114.208.7 (06/19 00:51)