Maximum number of circle packing into a rectangle

Question

I'm asked to pack the maximum number of 10m^2 circle into a 257 x 157m rectangle. After a lot of research, I found out that there are no optimal solution. So, i try to pack as many as possible (taking this website as reference):

1) First, I tried to place them in rectangular pattern:

• I had the width 257/d (diameter) -> I got about 72.024 --> So along the width, i can place 72 circle.
• I had the height 157/d (diameter) -> I got about 43.999 --> So along the height, i can place 43 circle.

--> That means in this case, i can fit in 43*72= 3096 circles

2) Then I try triangular pattern, which can fit more circles, 3575 circles. However, I find my math calculation kinda inefficient, long, and not correct in any other cases.

So my question is: Did I calculate it in a correct way? Are there any other more effective calculation methods?

Because in later question, it asks me to find the area of the circle to so that we get the maximum profit. Giving the profit of each circle is: P(a) = 200 - 200/a (a is the area of the circle)

Answer 1

Consider the following diagram of a triangular packing:

If the circles have radius $r$, then each pair of horizontal red lines is a distance $r$ apart, and they're a distance $r$ from the edges. Each pair of vertical blue lines is a distance $r \sqrt 3$ apart, and they're still a distance $r$ from the edges.

So if you want the triangular packing to have $m$ circles in each column, and $n$ columns, then the rectangle must be at least $(2m+1) \cdot r$ units tall and $(2 + (n-1)\sqrt3) \cdot r$ units long. (Also, if the rectangle is only $2m \cdot r$ units tall, we can alternate columns with $m$ and $m-1$ circles.)

If the rectangle is $257 \times 157$ and the radius of a circle is $\sqrt{\frac{10}{\pi}}$, then:

• If we make $257$ the vertical dimension, then the rectangle is a bit over $144 \cdot r$ units tall, and a bit over $(2 + 49\sqrt3) \cdot r$ units wide. So we can arrange the circles in $50$ columns that alternate between $72$ and $71$ circles, for $25 \cdot 72 + 25 \cdot 71 = 3575$ circles.
• If we make $157$ the vertical dimension, then the rectangle is a bit over $87 \cdot r$ units tall, and a bit over $(2 + 82\sqrt3) \cdot r$ units wide. So we can arrange the circles in $83$ columns that have $43$ circles each, for $3569$ circles.

We pick the first option, which gave us the greater value.

If you want to know the exact number of circles that can fit, there is nothing better to be done than this calculation. But you can estimate the number of circles that will fit by knowing that the limiting density of the triangular packing is $\frac{\pi}{2\sqrt 3}$.

The $257 \times 157$ rectangle has area $40349$, but at most a $\frac{\pi}{2\sqrt 3}$ fraction of that area can be used: at most area $\frac{40349 \pi}{2\sqrt 3} \approx 36592.5$. If all circles have area $10$, then at most $3659$ circles can fit in that area. As you can see, this is an overestimate, because we aren't using the space around the edges of the packing as efficiently as possible.