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
.

Tue Nov 28 13:57:00 EST 1995