
Computational Geo
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 divideandconquer.
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 divideandconquer
algorithm to compute the convex hull of a set of n points in
the plane.