Implement Graham's scan to compute the convex hull of points in the plane. Use your code to compute the "onion" of a set of n points: This is the set of nested convex polygons obtained by (1) computing the convex hull and removing it, (2) computing the convex hull of the remainder, and removing it, etc; repeating until no point is left.
Compute the onion of n points drawn randomly in a square (pick each coordinate in [0,1] randomly, uniformly) and count the number of layers. Let L_n be the average number of layers. Run your code for many values of n< 10^6 and estimate the growth of L_n as a function of n.
The goal of the exercise is to test the hypothesis that L_n grows like c*(n^a) for some constants c, a>0: experiment with many point sets to guess a plausible value of a. Hint: a/2.
Due: 11:59PM Thursday, April 13.