[演算] convex hull的O(n*log(n))解法
這段證明我覺得寫得很冗長
沒辦法很簡單的就知道我想要表達甚麼
而且課本上好像沒有這個演算法
只有稍微類似的演算法
希望有人可以幫我改的結構和邏輯好一點
附上圖之類的
----------------------
證明正確性的重點應該是
加入一個新的點之後
那個點會是新的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)