33-5 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(n^{1 - \epsilon})$ for some constant $\epsilon > 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 $\Theta(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 $\Theta(\lg n)$.

• Points drawn according to a two-dimensional normal distribution. The convex $p$ hull has expected size $\Theta(\sqrt{\lg n})$.

a. Given two convex polygons with $n_1$ and $n_2$ vertices respectively, show how to compute the convex hull of all $n_1 + n_2$ points in $O(n_1 + n_2)$ 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. ($\textit{Hint:}$ Recursively find the convex hulls of the first $n / 2$ points and the second $n / 2$ points, and then combine the results.)

(Omit!)