BrainDen.com - Brain Teasers
• 0

# more simple circles

## Question

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

## Recommended Posts

• 0

sq rt (N)?

##### Share on other sites
• 0

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

2 (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*r2. So the area of the smallest circumscribed circle must be so much more.. The area of the circle must be:

pi*R2 = N*pi*r2 + N*(5/6)*k*r2

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!

##### Share on other sites
• 0

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.

Edited by gavinksong
##### Share on other sites
• 0

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.

##### Share on other sites
• 0

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.

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.

##### Share on other sites
• 0

This problem is extremely hard.

One idea for finding a solution via computer...

A 2D physics simulation

##### Share on other sites
• 0

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

Let the circumscribed circle touches the inner circles at points p

0, p1, .. pm. Let r0, r1, .. rm be the radii that connects these points to the center of the circumscribed circle. Let these radii be at angles a0, a1, ..am to any fixed radius of the circumscribed circle. Then, I got these two interesting results (assuming the circumscribed circle has minimum radius):

sin(a0) + sin(a1) + .. + sin(am) = 0

and,

cos(a0) + cos(a1) + .. + cos(am) = 0

I can't prove these two yet "formally"

##### Share on other sites
• 0

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

Let the circumscribed circle touches the inner circles at points p

0, p1, .. pm. Let r0, r1, .. rm be the radii that connects these points to the center of the circumscribed circle. Let these radii be at angles a0, a1, ..am to any fixed radius of the circumscribed circle. Then, I got these two interesting results (assuming the circumscribed circle has minimum radius):

sin(a0) + sin(a1) + .. + sin(am) = 0

and,

cos(a0) + cos(a1) + .. + cos(am) = 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 by gavinksong
##### Share on other sites
• 0

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

Let the circumscribed circle touches the inner circles at points p

0, p1, .. pm. Let r0, r1, .. rm be the radii that connects these points to the center of the circumscribed circle. Let these radii be at angles a0, a1, ..am to any fixed radius of the circumscribed circle. Then, I got these two interesting results (assuming the circumscribed circle has minimum radius):

sin(a0) + sin(a1) + .. + sin(am) = 0

and,

cos(a0) + cos(a1) + .. + cos(am) = 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..

##### Share on other sites
• 0

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

Let the circumscribed circle touches the inner circles at points p

0, p1, .. pm. Let r0, r1, .. rm be the radii that connects these points to the center of the circumscribed circle. Let these radii be at angles a0, a1, ..am to any fixed radius of the circumscribed circle. Then, I got these two interesting results (assuming the circumscribed circle has minimum radius):

sin(a0) + sin(a1) + .. + sin(am) = 0

and,

cos(a0) + cos(a1) + .. + cos(am) = 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 by gavinksong
##### Share on other sites
• 0

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

##### Share on other sites
• 0

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

##### Share on other sites
• 0

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 by gavinksong
##### Share on other sites
• 0

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.

##### Share on other sites
• 0

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

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.