Sparse-hulled distributions Consider the problem of

Chapter 33, Problem 33-5

(choose chapter or problem)

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 expected size .n1=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 .plg n/. a. Given two convex polygons with n1 and n2 vertices respectively, show how to compute the convex hull of all n1Cn2 points in O.n1Cn2/ 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. (Hint: Recursively find the convex hulls of the first n=2 points and the second n=2 points, and then combine the results.)