I have an exercise in Computational Geometry. At first all statements look like very obvious and straightforward and this is misleading. All proofs should be very careful and very rigorous. Please take a look at exercise, after every question I tried to give a answer to it. If you fell that my proof is not right or should be changed, please fell free to change it.
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.
According to definition of convex hull, convex hull is the minimum convex set containing $S$ therefore obvious pieces of circles would be a boundary of convex hull, in addition all points that are convex combinations of the pieces of circles should be in convex hull all there combinations are straight line segments.
b. Show that each circle can occur at most once on the boundary of the convex hull.
In my opinion the task is not stated well. Actually I can't come up with such a example.
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'$.
If a center of any circle it's not a boundary of $S'$ then it can be expressed as convex combination of vertices of $S'$, therefore all point of this circle can be expression in terms of convex combination of vertices of $S$.
d. Give an $O(nlogn)$ algorithm for computing the convex hull of $S$.
I think the idea should be similar to Graham and Jarvis algorithms, first take the circle with the lowest position, then run on the chord of the circle and on every step check what is the first point of the current circle from which we can reach the nearest circle (in terms of degree of angle) by line segment and go to this circle. i don't know how exactly to implement it.