Convex Hull of Unit Circles

Question

I know that if we're trying to get the convex hull of $n$ unit circles, we can simply shrink the circles down to their centers and consider the convex hull of their centers, but I'm trying to prove some intermediate steps towards that.

a) Show that boundary of the convex hull consists of only straight line segments and parts of circles.

b) Show that each circle an appear at most once in the boundary of the convex hull.

(This is from de Berg's Computational Geometry book.)

I sort of have an intuition of why these are true, but my problem is that whenever I try to come up with a solution, I end up considering lots of cases, and I feel like it's not rigorous or elegant enough because of so many cases. Is there a neat way to prove these?

(Note: I know that this has been posted before in Convex Hull Algorithms, but I'm not satisfied with the answers there, and I'm trying to go for something more rigorous.)

Answer 1

For easier reference, denote the union of the finitely many circles by $S$ and denote the boundary of their convex hull by $B$. To show that $B$ consists of straight line segments and parts of circles, it suffices to show that every $b\in B$ is either in $S$ or on a straight line segment contained in $B$.

By definition $b$ is on the boundary of a half plane $H$ that contains $S$. Because $S$ is a closed set $H\cap S$ is nonempty. So if $b$ is the only point on $H$ that is contained in $S$ then $b\in S$, so $b$ is on a part of a circle. If there is another point on $H$ that is also on $B$, say $c$, then the straight line segment $\overline{bc}$ is contained in $B$, and this shows that $b$ is on a straight line segment contained in $B$.

This proves part a. Part b takes some more work because the statement you are asked to prove is false. To figure out the correct statement, first prove that:

If two antipodal points on a circle are contained in $B$, then all circle centers are collinear.

This quickly suggests the counterexample to part b that I give in the comments: If $n\geq3$ and all circle centers are collinear, then $n-2$ circles appear twice in $B$. So from now on consider only the nondegenerate case where the circle centers are not all collinear. In particular, no circle contains two antipodal points that are both contained in $B$.

Now to prove part b the following statement goes a very long way:

If two non-antipodal point on a circle are contained in $B$, then the shortest circular arc connecting the two is also contained in $B$.

This comes down to showing that in the picture below, where $b_1$ and $b_2$ are two points on the circle that are on the boundary of the convex hull, none of the circles meets the red regions:

For the two unbounded (more transparent) red regions this is immediate from the definition of the convex hull. For the small (opaque) red region this is an easy exercise in plane geometry; the center of any circle must be at least unit distance from both straight lines.

From the statement above it quickly follows that for any circle, the points that are contained in $B$ form a circular arc. So each circle appears at most once in $B$.

Answer 2

just a clarifying comment. a) the boundary of the convex hull of a family K of unit circles is the union of common outer tangential segments to pairs of circles and circular arcs connecting them b*) the supporting lines to K are tangents to a circle with a point on the boundary of K or a line containing a common outer tangential segment of two circles of K