How many circles can be placed inside another circle?

[rozan330]

We have a circle of certain radius.How many circles of smaller radius(we are provided with the ratio of radius) can be placed within the larger circle? Help me to determine the least number of the smaller circles that can be filled?? I am trying to generate a generalized solution, and looking for help??

 

[disregardthat]

I assume you mean the maximal amount, and not the least. Is your general solution supposed to be mathematical or a program?

 

[Gerenuk]

Do you mean something like
http://mathworld.wolfram.com/CirclePacking.html
http://www2.stetson.edu/~efriedma/packing.html
?

 

[rozan330]

First of all thank you, for showing interest in my problem.

I assume you mean the maximal amount, and not the least.
Yes, i wanted to say the least amount of gap, but it became otherwise.
Is your general solution supposed to be mathematical or a program?
I am working on this problem on mathematical basis and also reviewing the packing fraction concept for this. Till now I have got a solution that gives the certain no. of circles that can be filled but the area of gap unfilled by the circle may exceed the area of 2 or even more circles. Which I wanted to discuss about.


Do you mean something like
http://mathworld.wolfram.com/CirclePacking.html
http://www2.stetson.edu/~efriedma/packing.html
?

Yes I mean to solve something like in the second link. But I wanted a general solution that gives the max no. of circles that can be filled when the radius of two circles are provided.

 

[Gerenuk]

At least the link says that you can't write a perfect program, because apparently it takes years of mathematical proofs to find the true optimum.
http://www2.stetson.edu/~efriedma/cirincir/

To write a program is very complicated and you probably can only do it by extensive trial.

 

[I_am_learning]

At least the link says that you can't write a perfect program, because apparently it takes years of mathematical proofs to find the true optimum.
http://www2.stetson.edu/~efriedma/cirincir/

To write a program is very complicated and you probably can only do it by extensive trial.

Quite surprising fact.
If it takes mathematicians years to find out solution for a even a particular case then there is no way that a general solution would come plain and simple.

 

[Gerenuk]

Of course for very large ratios (many circles), the solution is mostly hexagonal packing. Maybe there is even a limit ratio from which on there is an algorithm which finds optimal packing by putting a large chunk of hexagonal packed circles and filling up the gaps.

I find the circle in square packing interesting, because you see transitions between hexagonal packing and square packing.

Quite often actually proofs of optimization problems are quite difficult. For example in 3D the single case of packing sphere in an infinite space seems to have a natural solution, but its hard to proof that this is really the best:
http://mathworld.wolfram.com/KeplerConjecture.html
After 400 years the proof is still not 100% checked.

 

[CRGreathouse]

Of course for very large ratios (many circles), the solution is mostly hexagonal packing. Maybe there is even a limit ratio from which on there is an algorithm which finds optimal packing by putting a large chunk of hexagonal packed circles and filling up the gaps.

I don't know if it will be that simple. On one hand, the hexagonal packing is scary-efficient; it's hard to imagine 'improving' on it much. On the other hand, the square packing is even more obvious and hard to improve on, yet I remember an example (sorry, no link!) along these lines: take a 1 000 000 x 1 000 000 square packed with unit squares; clearly the best solution is 1 000 000 000 000 squares lined up the usual way. Now expand the square to size 1000000.01. By tilting squares appropriately, (thousands) of new squares can be accommodated.

I wish I had the actual example... I know nothing of packing problems myself.

 

[Gerenuk]

take a 1 000 000 x 1 000 000 square packed with unit squares; clearly the best solution is 1 000 000 000 000 squares lined up the usual way. Now expand the square to size 1000000.01.

Well no, that's the point. You can use a hexagonal packing to fit in more circles comfortably. There will be 999999 circles horizontally, but there will be 1154700 rows!
I hope I didn't do a mistake, but it seems fairly logical that the boundary mismatch is not enough to make up for the hexagonal tight packing?!