Convex Hull Algorithms

Question

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

Answer 1

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.