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.