Consider the problem of computing the convex hull of a set of points in the plane that have been drawn according to some known random distribution. Sometimes, the number of points, or size, of the convex hull of n points drawn from such a distribution has expectation O(n^1 − ∈) for some constant ∈ > 0. We call such a distribution sparse-hulled. Sparse-hulled distributions include the following:

• Points drawn uniformly from a unit-radius disk. The convex hull has expected size Θ(n^1/3).
• Points drawn uniformly from the interior of a convex polygon with k sides, for any constant k. The convex hull has expected size Θ(lg n).
• Points drawn according to a two-dimensional normal distribution. The convex hull has expected size Θ(√lg n).

a. Given two convex polygons with n₁ and n₂ vertices respectively, show how to compute the convex hull of all n₁ + n₂ points in O(n₁ + n₂) time. (The polygons may overlap.

b. Show how to compute the convex hull of a set of n points drawn independently according to a sparse-hulled distribution in O(n) average-case time. Recursively find the convex hulls of the first n/2 points and the second n/2 points, and then combine the results.