# Convex Hull Algorithms

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.

Exercise:

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.

Thanks

-
a. your answer does not make any use of the definition of the boundary of a set. It should. -- c. asks for the proof of an if and only if statement. Your answer seems to adress only one direction. I also do not see how it proves that claim. no comments on b., d. –  user20266 Mar 21 '12 at 12:51
I agree that b isn't stated well. As stated, three circles with collinear centres make a counterexample. The intended statement was probably along the lines of "Show that if two non-trivial continuous pieces of a circle C are in the boundary of the convex hull then there is a continuous piece of circle C in the boundary of the convex hull which includes both of them". –  Peter Taylor Mar 21 '12 at 13:02
@PeterTaylor: In your example, isn't the CH just a rectangle with rounded edges? –  Louis Mar 21 '12 at 13:26
@Louis, yes, and both the straight edges are tangent to the circle in the middle, but on opposite sides. –  Peter Taylor Mar 21 '12 at 13:59
@PeterTaylor: This is just because of non-general position, but yeah, the intended statement is that if an open arc of a circle appears on the CH, then it is the only one. I wrote down what is needed below. –  Louis Mar 21 '12 at 14:05

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.
-