I think the reason you're not getting any answers is that you asked a rather long question that's almost entirely algorithmic, with little or no mathematical content, and answers can easily be found by searching the Web e.g. for "merging polygons". Here's a post in comp.graphics.algorithms that answers your question in the general case. For your simple case, I'd suggest a), which is much simpler to implement than b) and c). Note, however, that this sort of thing is prone to rounding problems -- if it's possible that one of your points lies exactly on the boundary of the other polygon, that's likely to spell trouble because you won't be able to detect that exactly when intersecting the lines and you somehow have to make sure that different intersection tests are consistent despite rounding, e.g. you have to make sure you don't miss an intersection because both lines emanating from a point on the boundary test as non-intersecting because of rounding.
Assume here that $S$ has at least three circles and general position centers.
For part (a) you might want to be a bit more careful. The convex hull of $S$ will be the intersection of all closed half-planes containing all of $S$. In particular, every point on the boundary will be on the line supporting one of these half-planes. So first restrict yourself to lines tangent to two of the circles. The intersection of all half-planes containing $S$ and tangent to two of the circles is almost what you want, but not quite, since if you have a circle incident on two of these lines the "corner" between them needs to be cut out by the arc between the two tangency points.
This leads to part (b). If you want an example, put 4 circles with their centers on the vertices of a large square. The statement to be proved is that the boundary of $s\in S$ appears on the boundary of the CH either not at all or in a connected arc.
The idea of this part is to sharpen (a) a little bit more: the CH of $S$, if it contains an arc of the circle $s\in S$ leaves $s$ and doesn't come back. To see this, suppose that $s$ is on the convex hull with neighbors $t$ and $u$, which means that the CH contains line segments that are bitangents to $s$ and $t$ and $t$ and $u$. All the circles lie entirely in the intersection of the associated half-spaces, with $t$ and $u$ on the boundary, which means, that, in particular lines tangent to $s$ and any of the other circles give half-spaces that don't contain both $u$ and $v$.
For (c), I am not quite sure what you are trying to get at. Anyway, suppose that $s, t\in S$ are on the boundary of CH($S$). By the above, there is a line tangent to $s$ and $t$ supporting a half-plane containing all of $S$. This isn't possible if the line through the centers doesn't support a half-space containing all of the centers (since the circles are all the same radius). The converse follows from the same geometric argument. (I can't easily draw a picture.)
Finally, you can put the pieces together:
- (c) says that you should first compute the CH of $X'$, which you surely know how to do in $O(n\log n)$ time.
- (b) says that the CH of the centers actually gives you the combinatorics of CH($S$)
- (a) says how to find the actual CH of $S$: look at the bitangents between circles corresponding to the edges of CH($S'$). This is constant time per edge, so you are all set.
Best Answer
If this is in 2D, Yes, you should just use a standard algorithm. The Graham scan is perfect for your application, as it will not waste much time beyond sorting. You can find code all over the web, including my own here.