Circle packing – How to get the minimum length?

Question

In an a past admission paper from a local university, I came across a problem I couldn't solve.

Given $n$ circles with their respective radii $r_1, r_2, \dotsc , r_n,$ we are to find the minimum width of a rectangle to encapsulate all the given circles. The placement of the circles, along with an example case may be found here:

The problem, as I see it, is identifying the overlapping portion of the segments determined by the radii of adjacent circles of different diameters, and deduct the length of any such overlapping segment from the total sum of the radii.

It may be because I have no training in geometry, or I'm simply missing something trivial, but I can't see a solution. How would you solve this?

Answer 1

I'm assuming that the circles have to be placed as illustrated tangent to the common edge in the order they are specified - that is, we're not shuffling the circles around to solve an arbitrary packing.

There will still be some tricky cases when adjacent circles are of significantly different diameters. However in the case where the circle sizes are sufficiently similar that each circle touches only its two immediate neighbours (and the end circles touch the sides of the rectangle), the distance between adjacent circle centres is simply the projected distance of the line between the two centres: $$d_i = \sqrt{(r_i + r_{i+1})^2 - (r_i - r_{i+1})^2 } $$ where $d_i \;(i=[1..n-1])$ is the distance increment from centre to centre.

The total width is then $$r_1+\sum_1^{n-1}{d_i}+r_n$$

For the illustrated case, that's $$2+2\sqrt{(9-1)}+2 = 4+2\sqrt {\bbox[1px]{8}} \approx 9.657$$