I want to know how many small circles can be packed into a large circle.
Looking at Erich's Packing Center it seems that packing is a non-trivial problem to solve.
My interest is practical rather than theoretical, so I don't really care about the absolute upper bound. I just want a good enough solution that doesn't waste too much empty space.
Also, I have a range of acceptable diameters for the small circles. So it's not necessarily a question of packing $x$ circles into $1$ circle, but packing $x, x+1, … x+n$ circles into a circle, and seeing which one looks nicer. For instance, looking at EPC, $16$ and $18$ circles in one circle seems to be much prettier than $17$ – so even if I was looking for $17$ ideally, I would compromise by either using smaller circles or fewer circles instead.
So to solve my problem, I need a general, easily computable algorithm for packing $n$ circles into $1$ circle. I suspect this does not exist (otherwise EPC wouldn't). What about a general, easily computable algorithm that packs $n$ circles into a circle "well enough"?
Best Answer
Some remarks:
Assuming the $N$ small circles $c_i$ have radius $r_i$ each and position $u_i = (x_i, y_i)$ and the big circle $C$ is centered around the origin and has radius $R$.
Then a feasible configuration $u = (u_1, \dotsc, u_N)$ is one where
F1: all small circles reside within the big one $c_i \subseteq C$
F2: all small circles do not intersect $c_i \cap c_j = \emptyset$ for $i \ne j$
The simplest algorithm would generate random configurations $u$ and check for $F1$ and $F2$.
One problem is, that if $C$ is choosen too tight, especially $\sum_i r_i^2 > R^2$ the algorithm might never find a feasible configuration.
Another simple approach is exhaustive search, trying all configurations. As this configuration space is continuous this is not really possible. However one might experiment with restricting the positions to some discrete grid. The problem here is the enormous number of configurations.
On top of this there might be optimality criteria, like minimizing the area of the bounding box of the small circles. Even then one might end up with lots of solutions, thanks to symmetry.
The next level is probably to try heuristic methods. E.g. simulated annealing, genetic optimization, ant colony optimization, force field methods, etc. etc. Recently neuronal networks came back into fashion.
And finally there might be exact methods. For these I would search literature.