Sparse-hulled distributions

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(n1-?) 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 Θ(n1/3) expected size.

• Points drawn uniformly from the interior of a convex polygon with k sides, for any constant k. The convex hull has Θ(lg n) expected size.

• Points drawn according to a two-dimensional normal distribution. The convex hull has expected size.

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

b. Show that the convex hull of a set of n points drawn independently according to a sparse-hulled distribution can be computed in O(n) expected time. (Hint: Recursively find the convex hulls of the first n/2points and the second n/2 points, and then combine the results.)