Round Shapes

You have three disks, with radius r1, r2, and r3, respectively. What is the smallest possible radius R of a plate on which all three disks fit completely on at the same time without overlapping?

Originally posted by talzamir
You have three disks, with radius r1, r2, and r3, respectively. What is the smallest possible radius R of a plate on which all three disks fit completely on at the same time without overlapping?

This seems kind of sloppy (so i'm not actually going to go through with it),but would it work if you first solved for all of the interior angles of the triangle that joins all of the centers of the 3 circles that has side lengths

a = (r_2 + r_3)
b = (r_1 + r_2)
c = (r_1 + r_3)

by using the law of cosines, then the law of sines.

Next bisect all of angles using the point of intersection from the bisectors as the one vertex for a new triangle that has side length "b" (assuming r_1>r_2>r_3) and solve for the remaining legs from the half angles and the law of sines, taking the larger of the legs to be r'

Once you have the legs, draw a circle of radius "R" = ( r_1 + r' ) centered on the point described by the bisector intersection of the original triangle.

Like I said, seems messy, is it a valid approach?

It makes a lot of sense. I wonder about this though.. imagine having three circles with radii 8, 7, and 2. It would seem that the plate needed has a diameter of 15 and only touches the two big circles. Replacing the circle triplet with a larger triangle with side lengths 15, 10, and 9 would not really apply? Perhaps the situation where one circle is so small that the plate only touches the other two needs be handled separately.

Still, yours is far more elegant than what I started with. A system of equations of the form

x^2 + y^2 = r1^2
(x-r1-r2)^2+y^2 = r2^2
(x-something)^2+(y-something)^2 = r3^2

the third circle has a somewhat more complex equation as the center depends r1, r2 and r3, but I suppose it can be found without much hassle. Those equations in place, add the fourth one -

(x-a)^2 + (y-b)^2 = R^2

and set a and b and R so that this equation has exactly one solution together with eq1 and one with eq2.. that is, the edges of the circles touch but don't cut.. and at most one with the third equation, assuming that r3 is the smallest of the three radii; the third circle may not overlap the edge of the plate, but if it is small enough, needn't touch it.

Would this look feasible? At this point at least it doesn't look pretty at all.

I ran the numbers through my approach, using your radii of 8,7,2 respectively like you said, which I agree, if my solution was correct should yield a large circle of radius 15, which my solution does not give.

I started with 3 circles of equal size, and extrapolated ( apparently falsely) that it would extend to any 3 circles in that type of arrangement. My solution give a circle that will encompass all 3 circles, but it is certainly not a minimum...

I'm not sure I understand your method just yet, ( none of this is easy without visuals), but I'm going to give it a closer look.

Hardly even a method yet, just an idea. I was just thinking that if I draw the circles as a system of equations, they are all of the form

(x-centerpoint_x)^2 + (y-centerpoint_y)^2 = radius^2

and in addition, take any two of the four equations and solve, you should get EXACTLY ONE solution, which for second-degree equations could make things easier as the discriminant has to be zero in each case.

I then started thinking of this in another way. If the plate has radius R and a circle inside it has radius r < R, then the distance from the center point of the plate to the center or the circle has to be R-r, which gets close to what you were thinking. You would be looking for three circles, all touching each other, and then a point from which the center points of those circles are at distance R-r1, R-r2 and R-r3, respectively. There are three things not known, the x and y coordinates of the center of the plate, and the radius R of the plate, and three equations, so it should be solvable in theory. In practice.. we'll see.

That method too requires handling separately the cases where only two of the three circles touch the edge of the plate, but that looks straight-forward enough. I'll work on that bit next.

My working so far (trying cartesian coordinates solution method)

Notation: circle a, circle b, circle c: circles in order of decreasing radius
a,b,c : radii of corresponding circles

assume circles a and b touch with their centres on a horizontal line: draw the line from the edge of circle a passing to the edge of circle b and going through their centres (circle a on left)

Let co-ordinate (0,0) be the centre of this line
the the position of the centre of circle a is (-b,0)
and the position of the centre of circle b is (a,0)

assume circle c touches a and b (and is above their centres)
let the centre of circle c be (x,y)
we can form the equations for the sums of the mutual radii
a+c = sqrt((x+b)^2 + y^2)
b+c = sqrt((x-a)^2 + y^2)

take the square of one equation from the square of the other, the y^2's cancel out and we can derive

x = (a-b)(c/(a+b) + 1)
y = sqrt((a+c)^2 - (c(a-b)/(a+b)+a)^2)

the smallest circle S containing a and b has it centre at (0,0) and radius (a+b)

draw a line from the centre of S, through the centre of c, to the edge of c

the length of this line is sqrt(x^2 + y^2) + c

so circle c fits within S if

sqrt(x^2 + y^2) + c <= a + b

if the above inequality is not true, then the smallest circle containing circles a,b and c will be larger than S and will touch the perimeters of all three circles.

Originally posted by iamatiger
My working so far (trying cartesian coordinates solution method)

Notation: circle a, circle b, circle c: circles in order of decreasing radius
a,b,c : radii of corresponding circles

assume circles a and b touch with their centres on a horizontal line: draw the line from the edge of circle a passing to the edge of circle b and going through their cen ...[text shortened]... ning circles a,b and c will be larger than S and will touch the perimeters of all three circles.

Ok, more progress.

We have
circle a (radius a, centre{-b,0})
circle b (radius b, centre{ a,0 })
circle c (radius c, centre{ x,y})

where
x = (a-b)(c/(a+b) + 1)
y = sqrt((a+c)^2 - (c(a-b)/(a+b)+a)^2)

we are looking for the containing circle r, radus r, centre {s,t}

we can write down 3 equations by joining lines from the centre of r through the centres of a,b,and c to the edge of r. Each of these lines is length r, i.e.

r = a + sqrt((s+b)^2 + t^2) [equation 1]
r = b + sqrt((s-a)^2 + t^2) [equation 2]
r = c + sqrt((s-x)^2 + (t-y)^2) [equation 3]

we can move the terms around and square each equation to eliminate the square roots:

(r - a)^2 = (s+b)^2 + t^2 [equation 1a]
(r - b)^2 = (s-a)^2 + t^2 [equation 2a]
(r - c)^2 = (s-x)^2 + (t-y)^2 [equation 3]

resist the temptation to eliminate t straight away, as the final two equations then get very complex, first expand all the squares:

r^2 - 2ra + a^2 = s^2+2sb + b^2 + t^2 [equation 1b]
r^2 - 2rb + b^2 = s^2-2sa +a^2 + t^2 [equation 2b]
r^2 - 2rc + c^2 = s^2-2sx +x^2 + t^2-2ty + y^2 [equation 3b]
noticing the the square terms of r,s and t in the equations are the same we rearrange all equations to:
r^2 -t^2 - s^2= b^2 +2sb + 2ra - a^2 [equation 1c]
r^2 -t^2 -s^2 = a^2 -2sa + 2rb - b^2 [equation 2c]
r^2 -t^2- s^2 =y^2 -2sx + 2rc - c^2 +x^2 -2ty [equation 3c]

now combining 1c and 2c we get:
b^2 +2sb + 2ra - a^2 = a^2 -2sa + 2rb - b^2 [equation 4]
rearranging
sb+sa = a^2 + rb -ra - b^2
s = a - b + (b-a)r/(a+b)

which is a nice simple term for s in terms of r

to be continued

carrying on:
so far we have got as far as
s = a - b + (b-a)r/(a+b) [equation 5]

going back to
r^2 -t^2 -s^2 = a^2 -2sa + 2rb - b^2 [equation 2c]
r^2 -t^2- s^2 =y^2 -2sx + 2rc - c^2 +x^2 -2ty [equation 3c]

we can get
a^2 -2sa + 2rb - b^2 = y^2 -2sx + 2rc - c^2 +x^2 -2ty

which can be rearranged to
t = (b^2 - a^2 - c^2 + y^2 + x^2 + 2sa - 2rb - 2sx + 2rc)/(2y)
t = (b^2 - a^2 - c^2 + y^2 + x^2 + 2s(a-x) - 2rb + 2rc )/(2y)

and using our definition of S from equation 5:

t = (b^2 - a^2 - c^2 + y^2 + x^2)/2y
+( (a - b + (b-a)r/(a+b) )(a-x) - r(b+c))/y

now we are on the home straight!

ok, the equations up to here check out
A search finds several integer solutions such as:

a=117, b = 39, c = 36
this gives
x = 96, y = 72
For these circles, a+b = r = 156
i.e the circle containing a and b also touches and contains c

Via a spreadsheet search I found 15 similar integer combinations of a,b and c where x and y are integers and a+b = r

the equations up to this point predict what the centre of S will be for these combinations, and for all of them the equations predict the centre {s,t} = {0,0} which is obviously correct.

So we are probably on solid ground for the final step...

So far we are trying to find a circle with radius r and centre s,t

we know:
s = a - b + (b-a)r/(a+b)

t = (b^2 - a^2 - c^2 + y^2 + x^2)/2y
+( (a - b + (b-a)r/(a+b) )(a-x) - r(b+c))/y

carefully separating these into bits that contain r, and bits that don't we have:
s = a - b + (b-a)/(a+b)r
t = (b^2 - a^2 - c^2 + y^2 + x^2)/2y
+(a - b)(a-x)/y
+(1/y)((b-a)(a-x)/(a+b)-(b+c))r

Defining:
U = a-b
V = (b-a)/(a+b)
W = (b^2 - a^2 - c^2 + y^2 + x^2)/2y +(a - b)(a-x)/y
Z= (1/y)((b-a)(a-x)/(a+b)-(b+c))

We can now write
s = U +Vr
t = W + Zr

so we can substitute these into equation 1a
(r - a)^2 = (s+b)^2 + t^2

giving:
(r-a)^2 = (U +Vr + b)^2 + (W + Zr)^2

multiplying out
r^2 - 2a + a^2 = (U+b)^2 + 2V(U+b)r + (Vr)^2 + W^2 + 2WZr + (Zr)^2

gathering r terms on the left
(1 - V^2 - Z^2)r^2 - (2V(U+b) + 2WZ)r = (U+b)^2 + W^2 + 2a - a^2

r^2 - ((2V(U+b) + 2WZ)/(1 - V^2 - Z^2))r =
((U+b)^2 + W^2 + 2a - a^2)/(1 - V^2 - Z^2)

(r - ((V(U+b) + WZ)/(1 - V^2 - Z^2)))^2 =
((U+b)^2 + W^2 + 2a - a^2)/(1 - V^2 - Z^2) + ((V(U+b) + WZ)/(1 - V^2 - Z^2))^2

r = ((V(U+b) + WZ)/(1 - V^2 - Z^2))
+ sqrt{ ((U+b)^2 + W^2 + 2a - a^2)/(1 - V^2 - Z^2) + ((V(U+b) + WZ)/(1 - V^2 - Z^2))^2}

and there we are!

we can put the value of r back into the expressions for s and t to find the centre of the circle.

I will now test out these equations. to make sure they are right

..wow! Those equations look accurate, but the outcome hard to visualize so far..?

Hmm, looks like I made a mistake in the last bit somewhere as with radi 23,22,21 the term inside the sqrt is -136.931
I will have to go over them again

Spotted an error!

s = a - b + (b-a)r/(a+b) is ok
but
t = (b^2 - a^2 - c^2 + y^2 + x^2)/2y
+( (a - b + (b-a)r/(a+b) )(a-x) - r(b+c))/y IS WRONG
it should be
t = (b^2 - a^2 - c^2 + y^2 + x^2)/2y
+( (a - b + (b-a)r/(a+b) )(a-x) - r(b-c))/y

this means that we get
s = a - b + (b-a)/(a+b)r
t = (b^2 - a^2 - c^2 + y^2 + x^2)/2y
+(a - b)(a-x)/y
+(1/y)((b-a)(a-x)/(a+b)-(b-c))r

which changes the value of Z so:
U = a-b
V = (b-a)/(a+b)
W = (b^2 - a^2 - c^2 + y^2 + x^2)/2y +(a - b)(a-x)/y
Z= (1/y)((b-a)(a-x)/(a+b)-(b-c))

then when I had
(r-a)^2 = (U +Vr + b)^2 + (W + Zr)^2

it should have multiplied out to
r^2 - 2ra + a^2 = (U+b)^2 + 2V(U+b)r + (Vr)^2 + W^2 + 2WZr + (Zr)^2

which then rearranges to (substituting a = U +b)
(1 - V^2 - Z^2)r^2 - 2r(Va + WZ + a) = W^2

so
r^2 - 2r(Va + WZ + a)/(1 - V^2 - Z^2) = W^2/(1 - V^2 - Z^2)

(r - (Va + WZ + a)/(1 - V^2 - Z^2))^2 =
(Va + WZ + a)^2/(1 - V^2 - Z^2)^2 + W^2/(1 - V^2 - Z^2)

r = (Va + WZ + a)/(1 - V^2 - Z^2) +
sqrt( (Va + WZ + a)^2/(1 - V^2 - Z^2)^2 + W^2/(1 - V^2 - Z^2))

gathering like terms we can say
D = (1 - V^2 - Z^2)
E = (Va + WZ + a)/D
r = E + sqrt(E^2 + W^2/D)

summarizing everything:
x = (a-b)(c/(a+b) + 1)
y = sqrt((a+c)^2 - (c(a-b)/(a+b)+a)^2)

{x,y} is the centre of circle c
circle a is centred at {-b,0}
circle b is centred at (a,0)

if sqrt(x^2 + y^2) + c <= a + b
then centre of containing circle is {0,0} and its radius is a+b

otherwise:
V = (b-a)/(a+b)
W = (b^2 - a^2 - c^2 + y^2 + x^2)/2y +(a - b)(a-x)/y
Z= (1/y)((b-a)(a-x)/(a+b)-(b-c))
D = (1 - V^2 - Z^2)
E = (Va + WZ + a)/D

r = E + sqrt(E^2 + W^2/D)
r is the radius of the containing circle, and it has centre {s,t} where
s = a - b + (b-a)r/(a+b)
t = (b^2 - a^2 - c^2 + y^2 + x^2 + 2s(a-x) - 2rb + 2rc )/(2y)


These equations have been checked by drawing circles a,b,c and the calculated containing circle in excel and they look perfect

good test for equations:

a = 84, b = 84, c = 75

containing circle centre {0,35} radius 175

a = 120, b = 120, c = 98
containing circle {0,35} radius 245

and a really good one:
a = 440 b = 385 c 330
c centre {77,616}
containing circle {-1,112} radius 840