How to maximize area of two circles inside a rectangle without overlapping?

Question

Two circles have to be drawn inside a rectangle of dimensions $W\times H$ such that the area of both circles is to be as large as possible without overlapping. Let the radii of the circles be $r_1$ and $r_2$

How do I go about formulating the constraints?

Thank you.

Answer 1

For TL;DR:

$$r_2=-\sqrt{2}\sqrt{W}\sqrt{H}+W+\frac{H}{2}$$

$$r_1 = \frac{H}{2}$$

There are numerous text on global optimisation of the circle packing problem eg this paper

Consider that a rectangle has a large range of ratios of $W/H$.

It may help to consider the range from 1 (a square) to $W=2H$. Note that for any values where $W$ is greater than $2H$ there will be no further optimisation as your limit was two circles, and this extra width will just be considered wasted space.

Now there is a known global optimum for packing two circles in a square, where each circle has the same radius. Consider that if the radii can be different then the optimum will be a greedy selection of the first circle followed by a greedy selection for the second circle. Assuming that $r_1$ and $r_2$ can be different, I would suggest that the global optimum (though I'm not sure how to prove this) can be found by implementing a greedy first selection algorithm in this case.

Consider that the first cirle diameter is set to $min(W,H)$.

This gives $$r_1=\frac{min(W,H)}{2}$$

Without loss of generality assume that this is $H$ so that the remaining widthways is $(W-H)$. As depicted:

$$\therefore r_1 = \frac{H}{2}$$ As $W-H$ approches 0, the cicle with $r_2$ becomes smaller until it only occupies the remaining space in the corner not used by the first circle.

As $W-H$ increases, then the second circle increases in size until it has the same area as the first circle (when $W=2H$), and the two circles sit side by side.

Now Determine $r_1,r_2$ in terms of $W, H$:

From the second figure we have: $$L_1=\frac{h}{2}-r_2$$ $$L_2=w-\frac{h}{2}-r_2$$ $$L_3=\frac{h}{2}+r_2$$

$L^2_3=L^2_1+L^2_2$ by pythagoras, and so expanding and simplifying

$$\Rightarrow \frac{H^2}{4}+r^2_2-HW-2Wr_2+W^2=Hr_2$$ $$\Rightarrow r_2=-\sqrt{2}\sqrt{W}\sqrt{H}+W+\frac{H}{2}$$

Note that this is based on the model that width is strictly equal or larger than height. If the height grows larger the solution can be applied by rotating the model such that the width becomes greater than the height.

Answer 2

I made program to draw as large as possible circles in a rectangle: