12
$\begingroup$

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

Suppose you have a $4' \times 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 point of maxima/minima and go from there.

My coworker did cut three $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

  • 1
    [Circle cutting is usually a nontrivial problem.](http://downloads.hindawi.com/journals/aor/2009/150624.pdf)2011-01-04
  • 0
    Erich's Packing Center http://www2.stetson.edu/~efriedma/packing.html has experimental results for many configurations, though I don't see circles in rectangles at a quick look.2011-01-04
  • 0
    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).2011-01-07

3 Answers 3

12

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

  • 0
    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?2011-01-04
  • 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](http://blog.stackoverflow.com/2010/08/new-image-upload-support/)).2011-01-04
  • 2
    This looks nice but the hard part is to prove "I believe the optimal configuration is as shown below...".2011-01-04
  • 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.2011-01-04
  • 0
    @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.2011-01-04
  • 0
    Thats exactly it. I was going in the wrong direction looking for an area function. This should work for a starting board of other proportions. I will give it a try.2011-01-04
  • 0
    @Brent: If the dimensions get significantly different or if the number of circles changes, I'm a lot less sure about the arrangement.2011-01-04
  • 0
    You could use the code I posted below to check if its correct for other dimensions or even bigger amount of circles (would require some small modifications).2011-01-04
  • 0
    @Isaac: Assuming(!) the three circles are tangent, you can reverse the problem by minimizing the rectangle instead of maximizing the circles: Fix two unit circles, w/ centers at (0,0) and (-1,0), and let a third have center $(2\cos\theta,2\sin\theta)$. For each $\theta$, find the area of the *smallest* $2Q$-by-$Q$ rectangle that *encloses* the trio. (This process should be straightforward, if tedious.) The min over all $\theta$ corresponds to the optimal configuration. (If *possibly* only two circles are tangent, put the third at distance $r$ from the origin and minimize over $r$, too. Messy.)2011-01-06
4

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.

  • 0
    I would be very surprised if Matlab can prove this. What was your input?2011-01-04
  • 0
    Matlab is more powerful than you think, check my post =)2011-01-04
  • 0
    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: http://mathoverflow.net/questions/31262/smallest-dilation-of-a-quadrilateral/32723#327232011-01-04
  • 0
    Sure but you can increase the mesh size to a point where you cover the whole function in a way that you can proove that you have found the global maximum with a really small error, and then its proven that the maximum has to be in that region. Its obvious that the analytic proposition of Isaac is correct then.2011-01-04
  • 0
    But you haven't done that! You can't just say that 10e-10 is very very small, you have to prove that it's small enough.2011-01-05
  • 0
    I agree thats why I said it can be done. You would have some more work to proove how the error in x limits the error in the function of r you want to optimize.2011-01-05
  • 1
    Well, exactly. So we agree that Matlab hasn't proved anything. (And neither have you.)2011-01-06
  • 0
    I already mentioned that is not a proof, I think you didn't get the intention of my post. I just wanted to show that a nummerical approach yields the same result as Isaac got and therefore supports his initial guess, not to give a proof (which has been done in the meantime by Christian). Maybe next time you can give constructive criticism or try to improove something yourself, instead of repeating the same point over and over again. What I meant in my last comment was that if you can show e.g. that the function is convex, the nummerical solution can be verified, in that case it is a proof.2011-01-06
  • 0
    We all saw exactly what you were doing with your post. It's not rocket science! But you claimed it was a proof. Now of course you're claiming that you didn't claim it was a proof. But you said: "Isaac had the right intuition." And: "Isaac found the analytic solution." As if you were contributing something with your silly floating-point approximations! Isaac's post had no need of them.2011-01-06
  • 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.2011-01-06
4

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'_+$.

  • 0
    That's very nice2011-01-06