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