Divide and Conquer

95.409 Course notes for Sep., 29,1999 - 3 -

Edited by: Mohammad Reza Nassji Matin (St.# 273952)

DIVIDE AND CONQUER

The third technique from the series of techniques for designing parallel algorithms is Divide and Conquer. This strategy consists of the following three basic steps:

1. Divide the problem into small subproblems of almost the same size.

2. Recursively solving each of the subproblems of above step.

3. Merging the solutions of the step 2, to find a solution for the main problem.

We illustrate this technique on one of the most famous Computational Geometry problems named the Convex-Hull problem.

Convex-Hull problem

First let’s see what the definition for a convex hull is:

Given a set S={p1, p2,…, p n} of n points in the plane, each represented by its (x, y) coordinates, the convex hull of S is the smallest convex polygon containing all the n points of S. In general we know that a polygon Q is convex if the line segment whose

endpoints are of any two points of Q, lies entirely in Q as shown in the figure1.

Now the convex-hull problem is to determine any ordered (preferably clockwise) list of the points in the convex hull of a set S.

Example: Consider the set of S points shown in figure1. In this case the convex hull of S is given by the ordered list (V1, V2, V3, V4, V5, V6, V7, V8). As we can see the points with the smallest and greatest X coordinates are on the convex hull.

V2 v4

V6

Figure1: the convex hull of the set of points

We can use Divide and Conquer strategy to solve the convex-hull problem. The T(n) of sequential algorithm to solve this problem is O( n log n) , whereas our parallel algorithm

as we will see uses an optimal number of operations, so its T(n) is O( log2 n) and its W(n) is O( n log n).

Remark: Before proceeding to the algorithm, for now consider that we can sort n numbers in O(log n) time on the EREW- PRAM using a total of O(n log n) operations.

This fact is proved in chapter 4 of JAJA book.

Assumptions: we have these assumptions to make the problem simple,

1. No two points in the set S have the same x or y coordinates.

2. We have n number of points in the plane where n is by power of 2.

3. Convex hull contains two parts, Upper Hull and Lower Hull; our algorithm finds the upper hull, finding the lower hull will be done in a similar way.

4. We know how to determine the upper hull of a convex hull of a set S if n<=4 by using the brute-force method.

5. For now we have a O(log n) sequential time procedure to compute the upper common tangent that uses a binary search method. Please note that in chapter 6 we will present a faster parallel algorithm for this purpose.

Before presenting the algorithm we define its Steps as follows, and for better understanding look at figure 2:

Step 1. We start by sorting the points in S according to their x coordinates. By noting the above Remark it will be done in O(log n) time using O(n log n) operations. Therefor we have:

x (p1) < x (p2) <… < x (pn) , where x (pi) is the x coordinates of the pi.

Step 2. Now we divide the points in S into two fair parts, left and right, so we have:

S1 = (p1, p2, … , pn/2) and S2 = (pn/2+1, … , pn).

And we recursively compute Upper Hulls.

Step 3. Now it’s the time for Merging the upper hulls found from step 2, by finding their upper common Tangent. As said in the assumption #5 this step’s time complexity is:

O(log |L| + log |R|) where L and R are the number of points in left and right divided parts of step 2, so it is O(log n).

Figure2: the line segment (a, b) is the upper common tangent of

The upper hulls of S1 and S2.

Now these are the questions that we are facing with:

Question 1: How much is the time complexity of our algorithm?

The answer to this question is O(log2 n)

Question 2: How much is the work complexity of our algorithm?

The answer to this question is O(n log n) or O(n log2 n).

In the next session we will present our algorithm more specific and we will compute the time and work complexities asked in above questions.