Consider the problem of computing the convex hull of a set of points in the plane that
Question:
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 Θ(√lg n).
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 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.
DistributionThe word "distribution" has several meanings in the financial world, most of them pertaining to the payment of assets from a fund, account, or individual security to an investor or beneficiary. Retirement account distributions are among the most...
Step by Step Answer:
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest