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.