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 CH (Q). For i > 1, define Q_i to consist of the points of Q with all points in convex layers 1, 2, . . . , i − 1 removed. Then, the i th convex layer of Q is CH (Q_i) if Q_i ≠ ∅ and is undefined otherwise.

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

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