Example: Computing a Convex Hull	Multithreaded Programming

Given X, a set of points in 2-D, the convex hull is the minimum set of points that define a polygon containing all the points of X. If you imagine the points as pegs on a board, you can find the convex hull by surrounding the pegs by a loop of string and then tightening the string until there is no more slack.

The following is an example of a convex hull of 20 points.



One way to compute a convex hull is to use the quick hull algorithm. Starting with two points on the convex hull (the points with lowest and highest position on the x-axis, for example), you create a line which divides the remaining points into two groups. If you find the convex hull of these two groups, they can be combined to form the convex hull of the entire set. Given the line and the set of points on one side of the line, find the point in the set furthest from the line. This point will also be on the convex hull. Using this point and the two endpoints of the line, you can define two new lines on which you can recurse. If you find a line with one or no points on the outside of the hull you have constructed so far, then you stop, knowing that both endpoints of the line and the one exterior point (if it exists) are in the convex hull.

The algorithm can be parallelized by running the recursive steps in parallel. The following code implements the QuickHull algorithm and a parallel QuickHull using the Task Programming Model.



You might be surprised to see how little extra code is necessary to turn a sequential algorithm into a parallel one. This is because the Task Programming Model takes care of many of the confusing, messy, and bug prone aspects of threaded programming.

Let's create some points to try the QuickHull algorithm on:




Now let's try the parallel algorithm:






As you can see, the relatively simple modification to add parallelism to the QuickHull algorithm leads to a good speedup.

Multithreaded Programming