Author |
Topic: Fitting Circles In A Rectangle (Read 18223 times) |
|
SWF
Uberpuzzler
Posts: 879
|
 |
Fitting Circles In A Rectangle
« on: Jul 1st, 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 2nd, 2003, 8:48am » |
Quote Modify
|
84? And the diameter is 1.01036297108184508789.
|
| « Last Edit: Jul 2nd, 2003, 9:03am by Leo Broukhis » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Fitting Circles In A Rectangle
« Reply #2 on: Jul 2nd, 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 3rd, 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 2nd, 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 2nd, 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 2nd, 2003, 4:37pm by Leo Broukhis » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Fitting Circles In A Rectangle
« Reply #5 on: Jul 3rd, 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 length-direction 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 3rd, 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: 13730
|
|
Re: Fitting Circles In A Rectangle
« Reply #6 on: Jul 3rd, 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 3rd, 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 conservative--a 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 3rd, 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: 13730
|
|
Re: Fitting Circles In A Rectangle
« Reply #8 on: Jul 3rd, 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 3rd, 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 3rd, 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: 13730
|
|
Re: Fitting Circles In A Rectangle
« Reply #10 on: Jul 3rd, 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: 13730
|
|
Re: Fitting Circles In A Rectangle
« Reply #11 on: Jul 3rd, 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 3rd, 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 double-check 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 4th, 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 23rd, 2003, 10:26pm » |
Quote Modify
|
I am pretty sure the value found by James of 32 is correct.
on Jul 3rd, 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 23rd, 2003, 10:27pm by SWF » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Fitting Circles In A Rectangle
« Reply #14 on: Sep 24th, 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 roughly-to-scale 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 M-1 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 not-too-complicated 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 easy--it 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 24th, 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 29th, 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 re-chargeable 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 2-dimensional 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 low-height 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 trial-and-error with a compass, or I can order the non-refundable batteries and do some real trial-and-error.
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 29th, 2012, 4:11am by the_dude » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Fitting Circles In A Rectangle
« Reply #17 on: May 29th, 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 29th, 2012, 11:13am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print