33-1 Convex layers

Given a set \(Q\) of points in the plane, we define the convex layers of \(Q\) inductively. The first convex layer of \(Q\) consists of those points in \(Q\) that are vertices of \(\text{CH}(Q)\). For \(i > 1\), define \(Q_i\) to consist of the points of \(Q\) with all points in convex layers \(i, 2, \dots, i - 1\) removed. Then, the \(i\)th convex layer of \(Q\) is \(\text{CH}(Q_i)\) if \(Q_i \ne \emptyset\) and is undefined otherwise.

a. Give an \(O(n^2)\)- time algorithm to find the convex layers of a set of \(n\) points.

b. Prove that \(\Omega(n\lg n)\) time is required to compute the convex layers of a set of \(n\) points with any model of computation that requires \(\Omega(n\lg n)\) time to sort \(n\) real numbers.

(Omit!)

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