# What is the smallest circle such that an arbitrary set of circles can be placed on the circumference without overlapping?

I have a set of circles of arbitrary radii: $r_1, r_2, r_3, ... r_n$.

I wish to arrange them around an inner circle so that they are all touching the perimeter of the inner circle, and do not overlap each other.

What I don't know how to do is figure out the inner radius $r_{inner}$.

I can figure out the angle each circle will use given an inner radius: $\theta_i = 2\sin^{-1} \frac{r_i}{r_i+r_{inner}}$, so I can test whether an inner radius is correct.

My first guess was to solve $2\pi = \sum_i (2\sin^{-1} \frac{r_i}{r_i+r_{inner}})$ for $r_{inner}$, but that's beyond my skills.

I also considered whether the sum of the diameters would equal the circumference of the circle, but that's a set of line segments rather than a smooth arc, and correcting that is also beyond me.

How do I figure out $r_{inner}$?

Numbers of circles around a circle is related, but assumes the circles are identical, which mine are not.

-
@l_e_a_h_c_i_m pointed out on twitter that the order of the circles matters - it will be different if it goes large-small-large vs large-middle-small. I'm most interested in the case where the circles are sorted large to small ($r_1$ largest), but I'm interested in the general case too. – dja Dec 5 '12 at 9:20

Using the cosine rule, the angle at the centre of the inner circle between lines through the centres of two adjacent touching circles is given by $$\varphi(i,{i+1}) \;=\; \cos^{-1}\left(\frac{R^2+R r_i+R r_{i+1}-r_i r_{i+1}}{(R+r_i) (R+r_{i+1})}\right)$$ where I've used $R$ instead of $r_{inner}$ for simplicity.

So, we need $$\qquad\qquad\qquad \qquad\qquad\qquad \sum\limits_{i=1}^n\varphi(i,{i+1})\;=\;2\pi \qquad\qquad\qquad \qquad\qquad\qquad(1)$$ where we consider $r_{n+1}=r_1$.

Using trigonometric identities, for a given $n$, it is possible to convert this into a very complex expression full of square roots, but there seems to be no easy way of solving the result in general (although for $n=3$ and $r_i=1,2,3$, we somewhat surprisingly get $R=\frac{6}{23}$).

Numerical solution is probably the best approach. (The diagram below was generated using Mathematica to solve numerically.)

Moreover, although this is a necessary condition, it is not sufficient in general because a sequence of small circles between two large circles may not fit tightly, causing the solution above to give an incorrect result (with the large circles overlapping):

$\qquad\qquad\qquad\qquad$

So for all $i\neq j$, for the above solution to be correct we also need $$\varphi(i,j) \;\geqslant\; \sum_{k=i}^{j-1}\varphi(k,{k+1})$$ with appropriate wrapping around of indexes if $i>j$. If this does not hold for some $i$ and $j$, then the correct solution for $R$ is obtained from $(1)$ by discarding circles $i+1,\ldots,j-1$. Due to the possibility of nested overlapping, the testing and discarding needs to be done iteratively, considering increasing values of $|i-j|$ in order.

-
perhaps more aesthetic is $$\mathrm{haversin}(\varphi(i,i+1))=\frac{r_ir_{i+1}}{(R+r_i)(R+r_{i+1})}$$ where $\mathrm{haversin}(\varphi)=\frac{1-\cos(\varphi)}{2}$ – robjohn Dec 12 '12 at 12:48
Upvotes can be so arbitrary -- seven people upvoted this question, you wrote a good answer with a nice diagram, and noone upvotes the answer... – joriki Dec 12 '12 at 18:03
I can imagine situations where the "discard" rule is more complicated. For example, take circles $12345$, where $1$ and $5$ are two large circles flanking two much smaller circles ($2$ and $4$) flanking a single very small circle ($3$). If $234$ are placed "naively" ($2$ tangent to $3$ which is tangent to $4$), then they are close enough together that they allow $1$ and $5$ to overlap, suggesting that the correct answer is found by discarding $234$. But if $3$ is small enough, then $2$ and $4$ overlap, and when this is corrected (by discarding $3$), $234$ can no longer be discarded. – mjqxxxx Dec 12 '12 at 21:07
@mjqxxxx: Thanks; I've updated my answer. – David Bevan Dec 13 '12 at 10:02
So ultimately it's a matter of solving numerically... Fair enough. I'll test that out and then accept it in the next couple of days. – dja Dec 14 '12 at 2:13

In the following diagram, $R$ is the radius of the center circle and $r_1$ and $r_2$ are two of the surrounding circles.

$\hspace{3cm}$

The Law of Cosines says $$(r_1+r_2)^2=(R+r_1)^2+(R+r_2)^2-2(R+r_1)(R+r_2)\cos(\varphi_{12})\tag{1}$$ which implies that \begin{align} \cos(\varphi_{12}) &=\frac{(R+r_1)^2+(R+r_2)^2-(r_1+r_2)^2}{2(R+r_1)(R+r_2)}\\[6pt] &=\frac{(R+r_1)(R+r_2)-2r_1r_2}{(R+r_1)(R+r_2)}\\[6pt] &=1-2\frac{r_1}{R+r_1}\frac{r_2}{R+r_2}\tag{2} \end{align} We need to find $R$ so that $$\pi=\sum_{i=1}^n\cos^{-1}\left(1-2\frac{r_i}{R+r_i}\frac{r_{i+1}}{R+r_{i+1}}\right)\tag{3}$$ where $r_{n+1}=r_1$. To this end, define $$f(x)=\pi-\sum_{i=1}^n\cos^{-1}\left(1-2\frac{r_i}{x+r_i}\frac{r_{i+1}}{x+r_{i+1}}\right)\tag{4}$$ and then $$f'(x)=\sum_{i=1}^n\frac{\frac1{x+r_i}+\frac1{x+r_{i+1}}} {\sqrt{\frac{x+r_i}{r_i}\frac{x+r_{i+1}}{r_{i+1}}-1}}\tag{5}$$ So we can use Newton's method to get the recursion $$x_{k+1}=x_k- \frac{\displaystyle\pi-\sum_{i=1}^n\cos^{-1}\left(1-2\frac{r_i}{x_k+r_i}\frac{r_{i+1}}{x_k+r_{i+1}}\right)} {\displaystyle\sum_{i=1}^n\frac{\frac1{x_k+r_i}+\frac1{x_k+r_{i+1}}} {\sqrt{\frac{x_k+r_i}{r_i}\frac{x_k+r_{i+1}}{r_{i+1}}-1}}}$$

-
This seems to be requiring that the angular ranges of the circles don't overlap. I think the intended requirement was only that the circles themselves don't overlap, which doesn't preclude their angular ranges from overlapping. – joriki Dec 12 '12 at 12:16
@joriki: I adjusted things – robjohn Dec 12 '12 at 19:19
Much better, but you don't mention the problem of large circles overlapping above small circles -- see David's answer. – joriki Dec 12 '12 at 20:16
@joriki: nor do I address the issue of whether $R$ changes for differing orders of the outer circles. Soddy's theorem would be useful for detecting the overlaps. I will add something about using Soddy's theorem. – robjohn Dec 12 '12 at 20:26
This appears to be very similar to the other answer: apart from different simplification of the angle and some extra solving of Newton's method, is there any real difference between the two? – dja Dec 14 '12 at 2:14