# what formula describes the convex hull of two circles (i.e. two circles connected by tangent lines)?

I'm investigating the following problem.

Imagine a circle at the origin with radius r. The circle moves upward with speed s and its radius simultaneously increases by a length of b per time unit. That is, at time t=0, the circle is at the origin with radius r. At time t=n, the circle is at (0, s*n) with radius r+b*n. As the circle moves and expands, it sweeps a shape. What is the formula for the shape swept by the circle in a given amount of time N?

It occurs to me that there are two cases. First, when s <= b, the motion of the circle is overshadowed by the expansion, and the final shape ends up being a circle at (0, s*N) with radius r+b*N.

But when s > b, the expansion can't keep up with the motion, and it sweeps a shape through space. It appears to me that the exact shape is that of both circles connected by line segments tangent to both, like two pulleys with a belt.

This related question says that it's called the convex hull of two circles. The questioner wants to know how to determine whether a point is within the convex hull. I could also like to know how, but I'd like to have a formula rather than an algorithm. I imagine there must be a formula that describes this shape, but unfortunately, I've been unable to derive one myself. :-/ It would be great if one formula handled both cases, but I'd be happy to have just the formula for case two.

I'd also be satisfied with a formula to determine the distance from the origin to the outer edge of the shape at a given angle. In fact, that is the main thing I would hope to calculate from the formula, in addition to using the formula to plot it.

Does anybody know? Thank you.

-
If you say the center at $t=0$ is the origin, then a point $(x,y)$ is in one of the circle's if and only if there exists a $t\in[0,N]$ such that $$x^2+(y-st)^2\le(r+xt)^2.$$ This can be rewritten as $(\text{quadratic in }t)\ge0$. You can find the interval(s) on $\mathbb{R}$ where this inequality holds using standard techniques and then check if one of them intersects $[0,N]$. The test for intersection can itself be written as an inequality in $N,x,y,s,$ and $r$ determined by the roots of the quadratic. – anon Aug 22 '11 at 1:44
Thanks, that looks promising. I will investigate after I get some sleep. In the question, I made a poor choice of variable name, using x for the increase (e.g. r + x*t) although it's unrelated to the x coordinate. I've renamed that to b. Am I correct that only the second x in your equation should be renamed to b, while the first x refers to the x coordinate? – Adam M. Aug 22 '11 at 2:15
I didn't even notice that slip up! Yes your understanding of the formula is correct. – anon Aug 22 '11 at 5:52
Hmm. Producing the (quadratic in t) >= 0 is easy enough. But it seems like the roots of the quadratic depend on both x and y. Then, finding the intervals where the inequality holds seems hard because it's not a 2d curve with a set of zero crossing points, but a 3d surface whose zero crossings are themselves curves (ellipses?). Getting the correct set of zero crossings also seems dependent on t being bounded. I'm probably just stating the obvious here, but I seem to have gotten stuck. I'll keep thinking about it, though, and hope I have some insight... :-) – Adam M. Aug 22 '11 at 12:36
It's a quadratic in t, there are only at most two roots. Remember $x,y,s,b$ are fixed. – anon Aug 22 '11 at 18:23

The phrase you want to research in general is "envelope of a family of curves". An envelope is a curve that's tangent to each member of the family at some point; in this case, it's the "border" of the shape swept out by your circles (though if your family doesn't extend indefinitely in both directions, you'll want to add circular caps at the top and the bottom).

It happens (as you suspect) that the envelope of your family consists of straight lines, and basic geometry should be able to prove this. However, it could easily have been the case that a more elaborate border curve arises, so I'll talk through your envelope as in this Wikipedia article. Note that the process involves taking "partial derivatives", so is technically an aspect of multi-variate calculus, although knowledge of basic single-variate calculus will do.

First, to reduce the number of parameters involved, let's say that the center moves as speed exactly $1$, and that radius increases at rate $k$. (Effectively, I'm just re-scaling your time parameter and setting $k := b/s$.) Note that, because you have discussed the case of the more-rapidly-increasing radius, we may assume $|k| < 1$.)

Now, at time $t$, the center of your circle is at $(0,t)$, and the radius is $r+kt$, so that

$$x^2 + (y-t)^2 = ( r + k t )^2$$

We define $F$ (so that the above is equivalent to $F = 0$) as

$$F := x^2 + (y-t)^2 - ( r + k t )^2$$

The equation of the envelope arises from setting $F$ and $\partial F/\partial t$ (the partial derivative of $F$ with respect to $t$) simultaneously equal to zero. We already know $F$. The partial derivative we seek is simply the derivative where we treat $x$ and $y$ as if they were constants (just as we do with $k$ and $r$).

$$\frac{\partial F}{\partial t}= 2 ( y - t )(-1) - 2 ( r + k t )(k) = 2 \left( t ( 1 - k^2 ) - ( y + k r ) \right)$$

Solving $\partial F/\partial t = 0$ for $t$ (and recalling $|k|<1$) ...

$$t = \frac{y+kr}{1-k^2}$$

... and substituting into $F = 0$ ...

$$x^2 + \left(y-\frac{y+kr}{1-k^2}\right)^2 - \left( r + k \frac{y+kr}{1-k^2} \right)^2 = 0$$

... yields ...

$$\left( 1 - k^2 \right) \left( x^2 \left( 1 - k^2 \right) - \left(yk+r\right)^2 \right) = 0$$

$$\implies x^2 \left( 1 - k^2 \right) = \left(yk+r\right)^2$$

$$\implies x \sqrt{ 1 - k^2 } = \pm \left(yk+r\right)$$

$$\implies x \sqrt{ 1 - k^2 } \mp y k = \pm r$$

... vindicating your suspicion that the border of the swept area consists of lines.

Specifically, when $k = 0$ (the circle's radius doesn't change as the its center climbs higher), we have a pair of vertical lines at distance $r$ from the $x$-axis:

$$x = \pm r$$

When $k \ne 0$, we have the lines with slope-intercept form

$$y = \pm \frac{\sqrt{1-k^2}}{k} x - \frac{r}{k}$$

The lines cross at $(0,-\frac{r}{k})$, where the circle (at time $t=-r/k$) collapses to a point.

All that said, you are now back to your question of finding an equation for the convex hull of your circles. I'll need to come back to this.

-
This is very interesting nonetheless. :-) – Adam M. Aug 22 '11 at 11:33

I will use the notation of @Day and consider only the right half of the hull ($x \ge 0$).

We have $$\cos \alpha = k, \;\;\; \sin \alpha = \sqrt{1 - k^2}, \;\;\; y_0 = r/k$$ So, the equation of the tangent is $$y(x) = x \sin \alpha / \cos \alpha -y_0$$ as was already derived by @Day. The hull is composed of the fragment $AB$ of the initial small circle, then the line segment $BC$ on the tangent and finally the fragment $CD$ of the moving growing circle. The hull can be described by the distance $R(\phi), -\pi/4 \le \phi \le \pi/4$ from the origin to the hull. Points inside the hull have Euclidean distance from the origin less or equal $R(\phi)$. Now, it is possible to derive implicit equations for $R(\phi)$ depending on the value of $\phi$ with respect to the angles given by $A, B, C, D$. I was not able to derive simple explicit formulae.

However, it possible to obtain explicit formulae for $x(y)$. The y-coordinates of the points are $$A_y = -r \;\;|\;\; B_y = -r sin \alpha \;\;|\;\; C_y = t - (r + kt) k \;\;|\;\; D_y = t + r + kt$$ The hull is characterized by: $$x(y) = \sqrt{r^2 - y^2} \mbox{ for } A_y \le y \le B_y$$ $$x(y) = (ky + r) / \sqrt{1 - k^2} \mbox{ for } B_y \le y \le C_y$$ $$x(y) = \sqrt{(r + kt)^2 - (y-t)^2} \mbox{ for } C_y \le y \le D_y$$

The left half of the hull is obtained by a simple reflection on the y-axis.

-

It may help you to have a more physical or alternate approach to think about this problem or the method of characteristics also see here too which is used to gain intuition for fluid like or wave like settings (e.g. a boat emitting a wake, a supersonic plane emitting shock waves, cars entering or leaving a traffic jam).

The idea is to plot $x$ (horizontal) vs $t$ (time). First you plot the trajectory of your boat. Then at each position the boat emit waves that travel to the right and left on the plot at the sound/wave speed. To find the area at time $t$ intersected you draw a horizontal line across the plot. Your two situations (where the area you want is a circle and where it is not a circle) correspond to your sound or wave source (the boat) traveling below or above the sound or wave speed. The analogy being that information is emitted at the sound speed and that gives you your circles. I find that these simple plots really help you think about where you get information when.

-