# Employing optimal packing, how many circles (51 mm diameter) can I cut from a rectangle (330 mm×530 mm)

I know that I should use some kind of honeycomb structure but can't work out in which orientation I should arrange it. I've looked at a few websites now and although I have a slightly better idea of the options, I can't work out how to model the problem and therefore calculate how many circles I could cut.

Specifically I would like to know:

~ How could I model this and what mathematics are involved?

~ What is the maximum number of 51 mm-diameter circles I can cut from a 330 mm × 530 mm rectangle?

~ What is the minimum size rectangle from which I could cut 16 circles?

(As you might suspect this is a real-life problem that I must solve, the disks that I will cut are to be used in a physics experiment but the material from which they are made is very expensive. It can however be purchased in any size rectangle, up to 330 mm × 530 mm.)

EDIT

OK so I just discovered this question and the Wikipedia link contained therein. Whilst it is certainly related I am no closer to solving my current queries. (Other than if I were to order a square sheet of the material measuring 204 mm × 204 mm but I'm sure a rectangle would be more efficient.)

-
In the title, and once in the text, you say that the long edge is 530 mm; but later you say 550 mm. – John Bentin Aug 10 '11 at 15:36
Right you are @John, I'll correct the typo, thanks. – qftme Aug 11 '11 at 10:38

## 2 Answers

For your problem, one choice is to order a rectangle with both dimensions a multiple of 51 mm, use a square pack, and get a density of $\frac{\pi}{4}\approx 0.785$

Another alternative is to use a hexagonal pack. If you have $k$ rows alternating $n$ and $n-1$ you want a sheet $51n \times (1+\frac{k \sqrt{3}}{2})51\ \$mm, which packs $\lfloor n(k-\frac{1}{2})\rfloor$ circles. For your case, $n=6, k=12$ will fit $66$ circles in $306 \times 537$ mm, with a packing density of about $0.8205$

For $16$ circles, you could also use a $4 \times 4$ hexagonal pack. This would require $230=4.5\cdot 51 \times 184\ \$mm, giving a density of $0.772$, so you could just buy $204 \times 204\ \$mm and be better off.

-
I haven't proven that there is not a more efficient way that doesn't follow the standard packs. However, those usually just use up the border around a standard pack. Since you can buy any size you want, it is probably better to choose a standard layout and buy the proper sheet. I have rounded up to the even mm in my answer. – Ross Millikan Aug 10 '11 at 15:37
The square packing has a constant density. The hexagonal pack will have a basic waste for a large area, plus waste proportional to the boundary. So you want the largest sheet (assuming it beats the square pack) because there are more interior points. – Ross Millikan Aug 11 '11 at 5:38
Thanks @Ross, that's exactly the info I needed. I don't quite understand what you've written in this phase though: "$230=4.5\cdot 51 \times 184\ \$mm", could you please clarify? – qftme Aug 11 '11 at 10:41
@qftme: I was just indicating where 230 came from as $4.5\cdot 51$, then that you needed 184 in the other direction. I agree it wasn't clear. – Ross Millikan Aug 13 '11 at 3:40

Since you don't say which websites you've looked at, I don't know whether you've discovered this one. Or this one. The main thing I get from these pages is that packing is hard, there are no general rules for optimal packings, but there are patterns that often work or are at any rate near-optimal.

-
I hadn't seen those particular links @Gerry. Thanks and +1. – qftme Aug 11 '11 at 10:42