Divide and Conquer 介紹

 1. 如果所有的點集合 |S| <=3,則直接使用暴力法解決 Convex Hull in O(1) time。 

 2. 否則找出一條垂直 x 軸的線,將所有點集合分成兩相同 size 集合  SL and SR 

 3. Recursively compute HL = Hull(L) and HR = Hull(R)

 4. Merge the two hulls into a common convex hull, H, by computing the upper and lower 

tangents for HA and HB and discarding all the points lying between these two tangents

 

1.

2.

3.

4.

回上一頁