Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hi I am new here and have a calculus question that came up at work.

Suppose you have a 4' x 8' piece of plywood. You need 3 circular pieces all equal diameter. What is the maximum size of circles you can cut from this piece of material? I would have expected I could write a function for the area of the 3 circles in terms of x and y, then differentiate it, find a maxima/minima point and go from there.

My coworker did cut 3 33" circles and that solved the real-world problem. But my passion would be to find the mathematical answer to this. I hope that my new stackexchange.com friends have the same passion, and can help me find the answer to this in general terms.

What I mean by that is someone says I have a piece of material Q units by 2Q units, what are the three circles of maximum size?... I hope you understand what I am asking. I am looking to be a friend and contributor BD

share|improve this question
1  
    
Erich's Packing Center www2.stetson.edu/~efriedma/packing.html has experimental results for many configurations, though I don't see circles in rectangles at a quick look. –  Ross Millikan Jan 4 '11 at 14:53
    
Christian Blatter has provided an elegant proof that Isaac's configuration is the best. So your problem is solved! If you agree, you should accept one of their answers (you can't accept both of them, unfortunately). –  TonyK Jan 7 '11 at 13:44

3 Answers 3

I believe the optimal configuration is as shown below, with the circles tangent to the sides of the rectangle and to one another.

diagram

Let the rectangle have sides of length $Q$ and $2Q$, as you specified, and let the radius of all three circles be $r$. Consider the right triangle with the segment joining the centers of the left and middle circles as its hypotenuse and with legs parallel to the sides of the rectangle.

diagram with triangle

The hypotenuse has length $2r$, and the legs have lengths $Q-r$ and $Q-2r$, so by the Pythagorean theorem, $(2r)^2=(Q-r)^2+(Q-2r)^2$. Solving for $r$ in terms of $Q$ gives $r=(3\pm\sqrt{7})Q$, but since $r<Q$, $r=(3-\sqrt{7})Q\approx 0.354249Q$. For your 4-by-8 board, that gives an optimal radius of approximately $0.354249\cdot 48\approx 17.0039$ inches, so a diameter of just over 34 inches.

share|improve this answer
    
I see that your images are from i.imgur.com. Do you draw these pictures on the website and then publish them, or you have to draw them on your computer and upload to the website? –  TCL Jan 4 '11 at 5:20
3  
@TCL: I used Mathematica to create the images in PNG form, then uploaded them--when writing a question or answer here, there is an "image" button in the toolbar which allows uploading an image file from your computer or from another web site, and it stores the image on imgur (see this blog post). –  Isaac Jan 4 '11 at 5:22
2  
This looks nice but the hard part is to prove "I believe the optimal configuration is as shown below...". –  AD. Jan 4 '11 at 6:48
1  
@Jasper: At the moment, I can't be sure (hence starting with "I believe..."), but I can't see how the packing of the circles could be tight unless 2 of the 3 circles are each tangent to two adjacent sides of the rectangle, and if that's correct, then I think there are only two possible configurations: the one shown ($r\approx 0.354249Q$) and one where the middle circle is along the bottom edge and the right circle is in the upper-right corner ($r\approx 0.345492Q$). If you can describe an arrangement where fewer than 2 circles are wedged into corners, but cannot be enlarged, I'll rethink it. –  Isaac Jan 4 '11 at 6:54
    
@Jasper: If the circles don't touch one another, I'd think there would have to be room to expand all the circles. It's not possible for the circles to be large enough to touch either pair of opposite sides of the rectangle. –  Isaac Jan 4 '11 at 7:08

Isaac had the right intuition.

alt text

I used Matlab to globally optimize the radius under the constrait that all three circles have the same radius, are in the rectangle and don't intersect each other. What I got is shown above,

R = 1.41699,

Pos1 = (6.58301,2.58301)

Pos2 = (1.41699,2.58301)

Pos3 = (4.0,1.41699)

Note that 1.41699"=17.00388 inches so Isaac found the analytic solution.

Due to request here the Matlab source (yes Matlab is indeed more powerful than u think):

circleradius.m:

%% x = [pos1X,pos1Y,pos2X,pos2Y,pos3X,pos3Y,r]
function f = circleradius(x)
f = -x(7); %% minimize the maximum :D

constraints.m

%% x = [pos1X,pos1Y,pos2X,pos2Y,pos3X,pos3Y,r]
function [c, ceq] = contraints(x)
c = [4*x(7)^2 - ((x(1) - x(3))^2 + (x(2) - x(4))^2); %% d(Circle1,Circle2)<=(2r)^2
4*x(7)^2 - ((x(1) - x(5))^2 + (x(2) - x(6))^2);
4*x(7)^2 - ((x(3) - x(5))^2 + (x(4) - x(6))^2); 
x(7) - x(1);  %% Circles are in the rectangle
x(7) - x(3); 
x(7) - x(5); 
x(7) - x(2);
x(7) - x(4);
x(7) - x(6);
x(7) + x(1) - 8; %% Width is 8
x(7) + x(3) - 8;
x(7) + x(5) - 8;
x(7) + x(2) - 4; %% Height is 4
x(7) + x(4) - 4;
x(7) + x(6) - 4;
-x(1); -x(2); -x(3); -x(4); -x(5); -x(6); -x(7)]; %% No negative values
ceq = [ ];

Later in main window:

[x,fval,exitflag] = patternsearch(@circleradius,[0.5000 1 1.5000 1 2.5000 1 0.5000],[],[],[],[],[],[],@contraints)
output of x >> 4.0000    2.5830    1.4170    1.4171    6.5830    1.4171    1.4170

Note that the values are truncated and the above is a solution which is symmetric to what I posted before. You can make it use a mesh of size 10e-10, so you are almost sure to get the global maximum, as the function is continuous. Also the result is faster and more reliable than NMinimize of Mathematica.

share|improve this answer
    
I would be very surprised if Matlab can prove this. What was your input? –  TonyK Jan 4 '11 at 19:29
    
Matlab is more powerful than you think, check my post =) –  Listing Jan 4 '11 at 22:07
    
I confess that I don't understand your Matlab code. But as you say, "you are almost sure to get the global maximum". I agree with this, but it's not a proof! For a similar problem, see my answer here: mathoverflow.net/questions/31262/… –  TonyK Jan 4 '11 at 22:15
1  
Well, exactly. So we agree that Matlab hasn't proved anything. (And neither have you.) –  TonyK Jan 6 '11 at 13:59
1  
"Tony", at least 2 people don't agree with you and found it useful. Also, funny how you first admit that you don't understand the really simple code and then say that its a "silly floating-point approximation". How do those two quotes say it is a proof, you just put something into them that they don't contain and +1 comment of you saying the same thing, hilarious. –  Listing Jan 6 '11 at 23:16

Let $Q:=[-2,2]\times[-1,1]$ be the given rectangle and let $r_0$ be the radius computed by Isaac for this rectangle. I shall prove that 3 circles of radius $r>r_0$ cannot be placed into $Q$ without overlap. The midpoints of these circles would have to lie in the smaller rectangle $Q':=[-2+r, 2-r]\times[-1+r,1-r]$. The left half $Q'_-$ of $Q'$ has a diameter $<2r_0<2r$ (by definition of $r_0$). It follows that $Q'_-$ can contain at most one center of non-overlapping circles of radius $r$, and the same is true for the right half $Q'_+$.

share|improve this answer
    
That's very nice –  TonyK Jan 6 '11 at 18:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.