[Parallel Algo.] 8. Divide & Conquer

Parallel Algorithm

8. Divide & Conquer

Main idea
      
      [1] Partition the input into subproblems of almost equal sizes
            將輸入分成幾乎相同大小的子問題

      [2] Solve recursively the subproblems in parallel
            平行且遞迴地解決每個子問題

      [3] Combine the solutions of the subproblems
            將每個子問題的輸出結合在一起

Example: Convex hull

      Input: a set S = {v1, v2, ..., vn} of n points
      Output: The convex hull CH(S) of S (clockwise)

      In the following figure, S is our input points, CH(S) is the output convex hull, 
      UH(S) is the upper hull of S and LH(S) is the lower hull of S.

Step 0, Sort all the points in S by their x coordinates. compute UH(S).

Algorithm UH(S)
Step 1, If |S| <= 4, then use a brute-force method to determine UH(S), and exit.
Step 2, Let S1 = {V1, V2, ..., Vn/2}and S2 = {Vn/2+1, ..., Vn-1, Vn}
Step 3, Recursively, do step 1 with S1 and S2.
Step 4, Find the upper common tangent between UH(S1) and UH(S2), and deduce UH(S)

Similarly, we can use this idea to find LH(S). Combine LH(S) and UH(S) to find CH(S).

D&G used in Step 2 ~Step 4, the Algorithm UH(S).