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(n² lg n). Show how to solve the on-line convex-hull problem in a total of O(n²) time.