Let S be a set of n (possibly intersecting) unit circles in the plane. We want to compute the convex hull of S.
a. Show that the boundary of the convex hull of S consists of straight line segments and pieces of circles in S.
b. Show that each circle can occur at most once on the boundary of the convex hull.
c. Let S be the set of points that are the centers of the circles in S. Show that a circle in S appears on the boundary of the convex hull if and
only if the center of the circle lies on the convex hull of S.
d. Give an O(nlogn) algorithm for computing the convex hull of S.
e.* Give an O(nlogn) algorithm for the case in which the circles in S have different radii.