1. In the on-line convex-hull problem, we are given the set Q of n points one point at a time. After receiving each point, we compute the convex hull of the points seen so far. Obviously, we could run Graham’s scan once for each point, with a total running time of O(n2lg n). Show how to solve the on-line convex-hull problem in a total of O(n2) time.
2. Show how to implement the incremental method for computing the convex hull of n points so that it runs in O(n lg n) time.