more simple circles

[BMAD]

Place N unit circles (radius=1) together without overlapping.  What is the smallest circle which can be circumscribed around the unit circles? 

[DeGe]

sq rt (N)?

[karthickgururaj]

sq rt (N)?

 

.. for it to be sqrt(N), the packing of circles must be 100% efficient (i.e, no loss of area). This won't be true even for large values of N..

 

.. we can ignore the "edge effects". Any non-edge circle will have 6 neighbors. The area "wasted" between any three circles can be easily calculated to be: (sqrt(3) - (pi/2))*r

² (where r is of course the radius). Let us define 'k = sqrt(3) - (pi/2)' . Since 6 circles will "waste" 5 times that area, the contribution of each circle towards wastage is: (5/6)*k*r². So the area of the smallest circumscribed circle must be so much more.. The area of the circle must be:

 

   pi*R² = N*pi*r² + N*(5/6)*k*r²

 

Yielding (for r = 1), R = sqrt((N/pi) * (pi + (5/6)*k))

 

sqrt(N) is correct to within 3% of the above expression..

 

 

.. may not be able to get a generic formula!

[gavinksong]

I don't have access to a computer, and I don't know how to use the spoiler mask on a phone. Hopefully, this post doesn't really warrant one.

Could someone point out how to mask things using only text?

Anyways, Karthick,

I think you should be careful with your assumptions. I'm not saying they are wrong, but your approach seems to assume that the optimal placement of circles will be the one that wastes the least space. Note that the optimal placement is actually the one where the maximum distance of any circle from the "center" is reduced, which isn't necessarily the one where the circles take up the least amount of total space.

PS. BMAD - You're really creative; you know that? I admire your prolificity in puzzle making.

Edited October 15, 2014 by gavinksong

[BMAD]

thank you gavinksong.

 

to type with spoilers, you can manually create them by typing "spoiler" in brackets not quotes to start your message, then type "/spoiler" in brackets not quotes when finished.

[karthickgururaj]

I don't have access to a computer, and I don't know how to use the spoiler mask on a phone. Hopefully, this post doesn't really warrant one.

Could someone point out how to mask things using only text?

Anyways, Karthick,

I think you should be careful with your assumptions. I'm not saying they are wrong, but your approach seems to assume that the optimal placement of circles will be the one that wastes the least space. Note that the optimal placement is actually the one where the maximum distance of any circle from the "center" is reduced, which isn't necessarily the one where the circles take up the least amount of total space.

PS. BMAD - You're really creative; you know that? I admire your prolificity in puzzle making.

I agree partly, gavinksong. However, because some area will be wasted between circles (even if they are packed optimally, solution I proposed places a lower bound on the value of the circumscribed radius.

[gavinksong]

This problem is extremely hard.

One idea for finding a solution via computer...

A 2D physics simulation

[karthickgururaj]

Also, even though it doesn't solve the OP,

Let the circumscribed circle touches the inner circles at points p

₀, p₁, .. p_m. Let r₀, r₁, .. r_m be the radii that connects these points to the center of the circumscribed circle. Let these radii be at angles a₀, a₁, ..a_m to any fixed radius of the circumscribed circle. Then, I got these two interesting results (assuming the circumscribed circle has minimum radius):

   sin(a₀) + sin(a₁) + .. + sin(a_m) = 0

and,

   cos(a₀) + cos(a₁) + .. + cos(a_m) = 0

 

I can't prove these two yet "formally"

[gavinksong]

Also, even though it doesn't solve the OP,

Let the circumscribed circle touches the inner circles at points p

₀, p₁, .. p_m. Let r₀, r₁, .. r_m be the radii that connects these points to the center of the circumscribed circle. Let these radii be at angles a₀, a₁, ..a_m to any fixed radius of the circumscribed circle. Then, I got these two interesting results (assuming the circumscribed circle has minimum radius):

sin(a₀) + sin(a₁) + .. + sin(a_m) = 0

and,

cos(a₀) + cos(a₁) + .. + cos(a_m) = 0

I can't prove these two yet "formally"

Can you show how you got this?

Off the top of my head, I feel like the case with five circles would be a counterexample...?

Edited October 16, 2014 by gavinksong

[karthickgururaj]

 

Also, even though it doesn't solve the OP,

Let the circumscribed circle touches the inner circles at points p

₀, p₁, .. p_m. Let r₀, r₁, .. r_m be the radii that connects these points to the center of the circumscribed circle. Let these radii be at angles a₀, a₁, ..a_m to any fixed radius of the circumscribed circle. Then, I got these two interesting results (assuming the circumscribed circle has minimum radius):

sin(a₀) + sin(a₁) + .. + sin(a_m) = 0

and,

cos(a₀) + cos(a₁) + .. + cos(a_m) = 0

I can't prove these two yet "formally"

Can you show how you got this?

Off the top of my head, I feel like the case with five circles would be a counterexample...?

 

Why would five circle case be a counter example?

 

My reasoning is thus:

consider the circumscribed circle to be a rubber-band that is squeezing the inner circles. Then the force that the rubber band exerts on the inner circles must all cancel out each other for the final system to be stationary. The equations follow if you take components of the force on x and y axis.

What I can't prove is that the force exerted by the rubber band is equal at all touch-points. But it "feels" so..

[gavinksong]

Also, even though it doesn't solve the OP,

Let the circumscribed circle touches the inner circles at points p

₀, p₁, .. p_m. Let r₀, r₁, .. r_m be the radii that connects these points to the center of the circumscribed circle. Let these radii be at angles a₀, a₁, ..a_m to any fixed radius of the circumscribed circle. Then, I got these two interesting results (assuming the circumscribed circle has minimum radius):

sin(a₀) + sin(a₁) + .. + sin(a_m) = 0

and,

cos(a₀) + cos(a₁) + .. + cos(a_m) = 0

I can't prove these two yet "formally"

Can you show how you got this?

Off the top of my head, I feel like the case with five circles would be a counterexample...?

Why would five circle case be a counter example?

My reasoning is thus:

consider the circumscribed circle to be a rubber-band that is squeezing the inner circles. Then the force that the rubber band exerts on the inner circles must all cancel out each other for the final system to be stationary. The equations follow if you take components of the force on x and y axis.

What I can't prove is that the force exerted by the rubber band is equal at all touch-points. But it "feels" so..

Ohh, I see what you were getting at now, Karthick.

I suppose it's in a similar vein as my suggestion that a 2D physics simutation could be used to find a solution, except you went out and made some hard mathematical observations. Pretty creative.

However, maybe your equations weren't phrased correctly or something? For instance, in the case of six circles (I know I said five earlier), I think intuitively the smallest arrangement would be in a ring formation. But if you move one of the circles from the outside of the ring to the center, the resulting arrangement would be the same size. In this case, your equations do not hold, especially since the outside circles are free to roll around the center circle.

Edited October 17, 2014 by gavinksong

[DejMar]

There does not appear to be a generic formula. If there were, I believe the Circle Packing article in Wolfram would have provided such. The article indicates that diameter of the circle inscribed with N unit-circles generally increases, but not always and sometimes the diameter of the next circle is actually smaller, with each unit-circle packed.

Where N is the number of unit-circles packed within a circle of diameter D.
N D
1 1
2 2
3 1 + 2/3*SQRT(3) = ~ 2.15470053837925
4 1 + SQRT(2) = ~ 2.41421356237309
5 1 + SQRT(1 + 1/SQRT(5)) = ~ 2.20300191001509
6 3
7 3
8 1 + csc(PI/7) ~= 3.30476487096249
9 1 + SQRT(2*(2 + SQRT(2))) = ~ 3.61312592975275
10 ~ 3.82...
...

[gavinksong]

The article indicates that diameter of the circle inscribed with N unit-circles generally increases, but not always and sometimes the diameter of the next circle is actually smaller, with each unit-circle packed.

Where N is the number of unit-circles packed within a circle of diameter D.

How is that possible? o.O

So if you packed five unit circle in the smallest circumscribing circle, and then removed a unit circle, the remaining unit circles suddenly wouldn't fit???

[gavinksong]

There does not appear to be a generic formula. If there were, I believe the Circle Packing article in Wolfram would have provided such. The article indicates that diameter of the circle inscribed with N unit-circles generally increases, but not always and sometimes the diameter of the next circle is actually smaller, with each unit-circle packed.

Where N is the number of unit-circles packed within a circle of diameter D.

N D

1 1

2 2

3 1 + 2/3*SQRT(3) = ~ 2.15470053837925

4 1 + SQRT(2) = ~ 2.41421356237309

5 1 + SQRT(1 + 1/SQRT(5)) = ~ 2.20300191001509

6 3

7 3

8 1 + csc(PI/7) ~= 3.30476487096249

9 1 + SQRT(2*(2 + SQRT(2))) = ~ 3.61312592975275

10 ~ 3.82...

...

It seems that you've made a small mistake.

The fifth diameter is 1 + SQRT(2(1 + 1/SQRT(5))), approx 2.7.

Nowhere else in the article does it say that the diameter of the circumscribing circle ever decreases.

Edited October 25, 2014 by gavinksong

[DejMar]

You are correct, gavinksong. I did make an error.  I suppose it is possible to find a function by mapping the the values and using extrapolation to find the polynomial, but I do not know if this has yet been done.

[bonanova]

You are correct, gavinksong. I did make an error.  I suppose it is possible to find a function by mapping the the values and using extrapolation to find the polynomial, but I do not know if this has yet been done.

 

For small numbers of circles the cluster is lumpy and erratic. One would expect an answer that is pretty much ad hoc. Which is to say that for the first n circles, it would take close to an n^th degree polynomial to give a good approximation to the smallest bounding radius. A table would be just as good.

 

By the same token, I'd bet there's a fairly simple asymptotic solution for large values of n.