     Next: Language Definition Up: Examples Previous: Primes

Planar Convex-Hull

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  to statistics . The algorithm we use to solve the problem is a parallel version  of the quickhull algorithm . 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 .     Next: Language Definition Up: Examples Previous: Primes

Jonathan Hardwick
Tue Nov 28 13:57:00 EST 1995