wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Fitting Circles In A Rectangle
        
(Message started by: SWF on Jul 1^st, 2003, 9:05pm)

Title: Fitting Circles In A Rectangle
Post by SWF on Jul 1^st, 2003, 9:05pm

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.

Title: Re: Fitting Circles In A Rectangle
Post by Leonid Broukhis on Jul 2^nd, 2003, 8:48am

[hide]84?[/hide] And the diameter is [hide]1.01036297108184508789[/hide].

Title: Re: Fitting Circles In A Rectangle
Post by towr on Jul 2^nd, 2003, 1:25pm

..[hide]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)[/hide]..

Title: Re: Fitting Circles In A Rectangle
Post by James Fingas on Jul 2^nd, 2003, 2:00pm

Hmm... I get [hide]45[/hide]. Using excessive trickiness, I might add ... ;D

Title: Re: Fitting Circles In A Rectangle
Post by Leonid Broukhis on Jul 2^nd, 2003, 4:33pm

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.

Title: Re: Fitting Circles In A Rectangle
Post by towr on Jul 3^rd, 2003, 1:52am

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.

Title: Re: Fitting Circles In A Rectangle
Post by towr on Jul 3^rd, 2003, 3:31am

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.

Title: Re: Fitting Circles In A Rectangle
Post by James Fingas on Jul 3^rd, 2003, 6:12am

I did a calculation that was evidently wrong. My answer now stands at [hide]32=8*4[/hide]. 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?

Title: Re: Fitting Circles In A Rectangle
Post by towr on Jul 3^rd, 2003, 7:13am

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

Title: Re: Fitting Circles In A Rectangle
Post by Leonid Broukhis on Jul 3^rd, 2003, 7:54am

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

Title: Re: Fitting Circles In A Rectangle
Post by towr on Jul 3^rd, 2003, 9:00am

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..

Title: Re: Fitting Circles In A Rectangle
Post by towr on Jul 3^rd, 2003, 9:59am

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

Title: Re: Fitting Circles In A Rectangle
Post by James Fingas on Jul 3^rd, 2003, 10:10am

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.

Title: Re: Fitting Circles In A Rectangle
Post by SWF on Sep 23^rd, 2003, 10:26pm

I am pretty sure the value found by James of [hide]32[/hide] is correct.

on 07/03/03 at 06:12:53, 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: [hide]11[/hide].

Title: Re: Fitting Circles In A Rectangle
Post by Barukh on Sep 24^th, 2003, 5:54am

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

Title: Re: Fitting Circles In A Rectangle
Post by James Fingas on Sep 24^th, 2003, 10:48am

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.

Title: Re: Fitting Circles In A Rectangle
Post by the_dude on May 29^th, 2012, 4:10am

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?

Title: Re: Fitting Circles In A Rectangle
Post by Grimbal on May 29^th, 2012, 11:13am

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.