The O(nlogn) algorithm to compute the convex hull of a set of n points

in the plane that was described in this chapter is based on the paradigm

of incremental construction: add the points one by one, and update the

convex hull after each addition. In this exercise we shall develop an

algorithm based on another paradigm, namely divide-and-conquer.

a. Let P1 and P2 be two disjoint convex polygons with n vertices in total.

Give an O(n) time algorithm that computes the convex hull of P1 ∪P2.

b. Use the algorithm from part a to develop an O(nlogn) time divide-andconquer

algorithm to compute the convex hull of a set of n points in

the plane.