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!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用