Author 
Topic: Fitting Circles In A Rectangle (Read 12781 times) 

SWF
Uberpuzzler
Posts: 879


Fitting Circles In A Rectangle
« on: Jul 1^{st}, 2003, 9:05pm » 
Quote Modify

If M and N are integers, it is easy to fit M*N circles of 1 cm diameter into an M cm by N cm rectangle without the circles overlapping. What is the smallest value of M*N such that an M cm by N cm rectangle can contain M*N identical circles, each with diameter greater than 1 cm? M and N must be integers. All circles must fit entirely within the rectangle at the same time, no circle may overlap any other circle.


IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Fitting Circles In A Rectangle
« Reply #1 on: Jul 2^{nd}, 2003, 8:48am » 
Quote Modify

84? And the diameter is 1.01036297108184508789.

« Last Edit: Jul 2^{nd}, 2003, 9:03am by Leo Broukhis » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Fitting Circles In A Rectangle
« Reply #2 on: Jul 2^{nd}, 2003, 1:25pm » 
Quote Modify

..I think 8*6=48, but I'm not quite sure, since my numbers change every 10 minutes (had lots of errors in my method)..

« Last Edit: Jul 3^{rd}, 2003, 3:33am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Fitting Circles In A Rectangle
« Reply #3 on: Jul 2^{nd}, 2003, 2:00pm » 
Quote Modify

Hmm... I get 45. Using excessive trickiness, I might add ...


IP Logged 
Doc, I'm addicted to advice! What should I do?



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Fitting Circles In A Rectangle
« Reply #4 on: Jul 2^{nd}, 2003, 4:33pm » 
Quote Modify

As neither towr, nor James specified the diameter, I tend to believe that they were solving a different problem: what is the smallest value of M*N such that an M cm by N cm rectangle can contain more than M*N identical circles, each with diameter 1 cm.

« Last Edit: Jul 2^{nd}, 2003, 4:37pm by Leo Broukhis » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Fitting Circles In A Rectangle
« Reply #5 on: Jul 3^{rd}, 2003, 1:52am » 
Quote Modify

Just because I don't know the diameter doesn't mean larger circles don't fit. And in my case I think it does, and I'm sure that's also the case in James' solution. If you take a length 8, height 6 box, you can put 7 layers of 7 (diameter 1) circles in it. And there is also room left at the top, so that the circles can be bigger since they can expand in height, and length. It's easy to calculate that there is actually space left at the top, and since 7 is smaller than 8 there is space in the lengthdirection as well. The diameter wasn't asked, but if you want it this should give enough information to find it, somehow.. And yes, incidentally it also fits one circle more. Even when they're all bigger.

« Last Edit: Jul 3^{rd}, 2003, 2:31am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Fitting Circles In A Rectangle
« Reply #6 on: Jul 3^{rd}, 2003, 3:31am » 
Quote Modify

I think there was still an error in my last result, but with MxN=9x7 I get a maximum diameter (2r) of 1.008234938 and it fits 8 rows of 8 circles (again one more than needed) The distance (d) between circles in the same row is about 0.05733373693 each rows adds about 0.8559664362 to the height (h), (h = sqrt( (2r)^2 (r + d/2)^2)) 7*0.8559664362+1 ~= 7 = N And this time there's also enough extra room left on the side to actually fit the even rows.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Fitting Circles In A Rectangle
« Reply #7 on: Jul 3^{rd}, 2003, 6:12am » 
Quote Modify

I did a calculation that was evidently wrong. My answer now stands at 32=8*4. The M*N circles can be larger by a very very small amount. I've experimented with other strategies, but I think this one is optimal. As for an exact diameter, I don't have one, but I know you can make them at least 1.00000235 cm in diameter (quite conservativea better calculation is too messy for me right now, but probably you could get 1.00001 cm diameter). Here's a related question: What if M,N were real numbers?

« Last Edit: Jul 3^{rd}, 2003, 6:17am by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Fitting Circles In A Rectangle
« Reply #8 on: Jul 3^{rd}, 2003, 7:13am » 
Quote Modify

I'm still quite a way off from James' 8*4 solution, but I have a 8*7 solution as well now.. with a diameter of 1.010536669

« Last Edit: Jul 3^{rd}, 2003, 7:22am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Fitting Circles In A Rectangle
« Reply #9 on: Jul 3^{rd}, 2003, 7:54am » 
Quote Modify

I can see that my solution can be trimmed to 7*8, though surprised by the slight difference in diameter wrt towr's solution.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Fitting Circles In A Rectangle
« Reply #10 on: Jul 3^{rd}, 2003, 9:00am » 
Quote Modify

Perhaps we have different solutions for the configuration of the circles that just happen to have the same M*N I think I might also be able to get James' solution, but the numbers are a bit tricky..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Fitting Circles In A Rectangle
« Reply #11 on: Jul 3^{rd}, 2003, 9:59am » 
Quote Modify

I get a possible diameter of 1.000039505 for an 8*4 solution. And it might not even be the max yet.. On the other hand I could have easily screwed up the equations.. but I have faith..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Fitting Circles In A Rectangle
« Reply #12 on: Jul 3^{rd}, 2003, 10:10am » 
Quote Modify

towr, That sounds like it's in the right ballpark. The only reason I know I didn't screw up the equations is that I didn't use any ... not this time anyways ... UPDATE: I worked out some equations then solved numerically, and my maximum size seems to be 1.000039015 cm. But it's possible I screwed up somewhere, and it looks like there are other smaller optimizations that I could make. UPDATE 2: Aha! I have a better method. Now I get a maximum size of 1.000045828. But maybe there are even more optimizations... UPDATE 3: Doh! I screwed up the calculations for that improved method, and it gives 1.000039506. But that doesn't matter, because I've got a better method that gives 1.00007615 now! Hmm ... better doublecheck my calculations... UPDATE 4: I have modified my better method to produce something close to optimal. I don't think it's worth refining the answer any more (due to diminishing returns). My maximal diameter is now 1.000104938, and I've rigorously checked it with a simulation.

« Last Edit: Jul 4^{th}, 2003, 8:17am by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



SWF
Uberpuzzler
Posts: 879


Re: Fitting Circles In A Rectangle
« Reply #13 on: Sep 23^{rd}, 2003, 10:26pm » 
Quote Modify

I am pretty sure the value found by James of 32 is correct. on Jul 3^{rd}, 2003, 6:12am, James Fingas wrote:Here's a related question: What if M,N were real numbers? 
 I think I have the answer to James' additional challenge: 11.

« Last Edit: Sep 23^{rd}, 2003, 10:27pm by SWF » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Fitting Circles In A Rectangle
« Reply #14 on: Sep 24^{th}, 2003, 5:54am » 
Quote Modify

I would like to see the explanations/simulations, please.


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949

Barukh, Okay, you asked for it! Here is a full description of the proposed solution, with a roughlytoscale diagram showing the solution. To find the minimum M and N, we will use a hexagonal packing arrangement. From here on in, the "height" of the box (M) will be filled alternately with columns of M circles and columns of M1 circles. In this way, we will be able to fit more than N columns into a box of width N. Simple calculation will show that we can fit 9 columns into a box 8 cm wide, but can't for any N<8. Another simple calculation will show that we need the box to be 4 cm high, giving 4*5+3*4 = 32 circles, before we can fit M*N circles of 1 cm in. This is evidently the minimum that we could ever reach. But can we fit in circles of greater than 1 cm diameter? Yes. There are many ways, but a nottoocomplicated method that gives results very close to optimal is shown in the diagram below. This packing is defined by two angles: [theta] and [phi], as shown in the diagram. This gives an "S" or "Z" shape to the columns of four circles (they alternate directions). The columns of three circles are packed in so that two of the circles touch, and the other circle doesn't. The calculations are done as follows: Pick values for [theta] and [phi]. From these values, calculate the acceptable maximum diameter of circle (using the height of the columns of four circles). Using that diameter, compute the locations of the three circles in the column of three circles. The solitary circle is easyit just touches two of the circles in the column of four. The other two are harder. Now calculate the offset from one column of four to the next. There are two ways to calculate this: one uses the solitary circle in the column of three, and one uses the touching circles. [theta] and [phi] should be chosen so that these two methods give the same offset. Multiply this offset by 4, and add d+d*sin[theta], to give the width of all 9 columns. [theta] and [phi] must be chosen so that this is less than 8 cm. Do all these calculations, then choose the largest possible values for [theta] and [phi]. You will get you the maximal value for d with [theta]=1.358 degrees and [phi]=0.675 degrees. There is still room for improvement, because the circles in the bottom left and top right corners can move into the corners, allowing a little extra room for all, but this is computationally intensive (the columns of 4 wouldn't all be the same any more), and would give us only a small improvement. My "simulation" involved computing the positions of the centers of all the circles in the first three columns and the last column, then seeing how far apart they were from each other and from the sides of the box in terms of d. They are all at least d apart from their neighbours.

« Last Edit: Sep 24^{th}, 2003, 10:57am by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



the_dude
Newbie
Posts: 1


Re: Fitting Circles In A Rectangle
« Reply #16 on: May 29^{th}, 2012, 4:10am » 
Quote Modify

OK, I know that's likely an easily formula, but if I could get a tad bit of help making it easier... I often need to fit Lithium Iron Phosphate battery cylinders into rectangular boxes as densely as possible to create rechargeable battery packs for specialized electric bicycle (green commuting) applications. I know the length of the cylinders, and I can select the corresponding box dimension to accommodate that length, plus a bit for a battery management PCB. That leaves me with a 2dimensional problem. Looking at the cylinders, and chosen box, from the end, the cylinders are circles, fitting into a rectangle. And I have trouble calculating in advance how many cylinders of r radius will fit into a rectangular box of x length and y height. My problem is that, for some lowheight boxes, I want to be able to slightly spread out the cylinders so that the next row sinks into the first row a bit deeper, but I don't have a good formula to calculate that. Can someone help? Here's the example at hand:   o o o  68mm height o o o o  200mm length Cylinders are 20mm radius (40mm diameter) I know the width of the bottom row if the circles were tight against each other; and I can figure out the formula to calculate the total height of two rows if the top 3 circles were just then resting in the crevices. In that case, the height of two rows would be [2 + sqrt(3)]r. Easy enough... and put more simply, the height is about 93.3 percent of what it would be if I stacked two rows... But here, I've got 4 circles that I can spread out evenly over the 200mm with three gaps between them, which, at their narrowest, are each 13.33mm. That lets the top row of 3 cylinders drop down lower, but I'm not sure how much lower. I can do some trialanderror with a compass, or I can order the nonrefundable batteries and do some real trialanderror. Can someone help me with some good formulae to use as tools to work out such problems in advance? I'm kinda stuck with certain, standard battery box sizes, and certain, standard battery diameter sizes (for example, there is an alternative battery which is 38mm diameter (19mm radius). How many of each of these types of circles (40 and 38) can I fit into this box? And what's my formula for the future, especially if I end up having more rows to work with?

« Last Edit: May 29^{th}, 2012, 4:11am by the_dude » 
IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7408


Re: Fitting Circles In A Rectangle
« Reply #17 on: May 29^{th}, 2012, 11:13am » 
Quote Modify

I don't think there is a simple formula. If you look at this http://en.wikipedia.org/wiki/Circle_packing_in_a_square you will see how irregular the optimal arrangements can be. There is no simple formula. Maybe you should use soda cans, measure them and build rectangular boxes to scale and see how many you can fit in. Or simpler, cut out cardboard circles with the exact size and play with that.

« Last Edit: May 29^{th}, 2012, 11:13am by Grimbal » 
IP Logged 



