The one-dimensional circle packing problem is as follows: You have N circles of radii r1, r2, . . . , rN. These circles are packed in a box such that each circle is tangent to the bottom of the box and are arranged in the original order. The problem is to find the width of the minimum-sized box. Figure 10.77 shows an example with circles of radii 2, 1, 2 respectively. The minimum-sized box has width 4 + 4 √2.

9.656 2 2