Our next example solves the planar convex hull problem: given n
points in the plane, find which of these points lie on the perimeter
of the smallest convex region that contains all points. The planar
convex hull problem has many applications ranging from computer
graphics [21] to statistics [27]. The
algorithm we use to solve the problem is a parallel
version [12] of the quickhull
algorithm [36]. The quickhull algorithm was given its
name because of its similarity to the quicksort algorithm. As with
quicksort, the algorithm picks a ``pivot'' element, splits
the data based on the pivot, and is recursively applied to each of the
split sets. Also, as with quicksort, the pivot element is not
guaranteed to split the data into equally sized sets, and in the worst
case the algorithm will require 
work.
Figure 8 shows an example of the quickhull algorithm, and
Figure 9 shows the code. The algorithm is based on the
recursive routine hsplit. This function takes a set of points
in the plane ( 
coordinates) and two points
p1 and p2 that are known to lie on the convex hull, and returns
all the points that lie on the hull clockwise from p1 to
p2, inclusive of p1, but not of p2. In
Figure 8, given all the points [A, B, C, ..., P],
p1 = A and p2 = P, hsplit would return the sequence
[A, B, J, O]. In hsplit, the order of p1 and p2
matters, since if we switch A and P, hsplit would
return the hull along the other direction [P, N, C].
Figure: Code for Quickhull. Each point is represented
as a pair. Pattern matching is used to extract the x and
y coordinates of each pair.
The hsplit function works by first removing all the elements that cannot be on the hull since they lie below the line between p1 and p2. This is done by removing elements whose cross product with the line between p1 and p2 are negative. In the case p1 = A and p2 = P, the points [B, D, F, G, H, J, K, M, O] would remain and be placed in the sequence packed. The algorithm now finds the point furthest from the line p1-p2. This point pm must be on the hull since as a line at infinity parallel to p1-p2 moves toward p1-p2, it must first hit pm. The point pm (J in the running example) is found by taking the point with the maximum cross-product. Once pm is found, hsplit calls itself twice recursively using the points (p1, pm) and (pm, p2) ((A, J) and (J, P) in the example). When the recursive calls return, hsplit flattens the result (this effectively appends the two subhulls).
The overall convex-hull algorithm works by finding the points
with minimum and maximum x coordinates (these points must be on
the hull) and then using hsplit to find the upper and lower
hull. Each recursive call has a depth complexity of 
and a work
complexity of 
. However, since many points might be deleted on
each step, the work complexity could be significantly less. For m
hull points, the algorithm runs in 
depth for
well-distributed hull points, and has a worst case depth of
.