# Circle packing with a twist

A quick look at Wikipedia makes it quite clear that circle packing is an open question in mathematics, with only n<20 having efficient packings and many of those are merely conjectured.

My question is slightly different, but related and therefore probably cannot be "trivially" solved either, I just want to ask you guys before giving up on it.

Imagine you have a circle of diameter D and n circles of diameter d (all of these are known values). What is the most efficient packing of the smaller circles (d) at the bottom of the larger circle (D)?

To better understand the question, imagine you have a tube through which cables pass. The cables do not fully pack the tube and therefore have room to settle to the bottom of the tube, leaving empty space at the top. How does one find the most efficient packing of the cables within the tube, considering efficiency as "how low can the center of mass of the cables go?"

-

Let $q^i$ be the position of the $i$th small circle. You are basically trying to solve the constrained optimization problem
$$\min_q \sum_i q^i_y\quad \textrm{s.t.}\quad \|q^i-q^j\|^2 \geq d^2,\ \|q^i\|^2 \leq (D-d)^2/4.$$
This problem is unfortunately not convex. Software packages exist that will tackle it for you (the keyword you can start with is quadratically-constrained quadratic programming problem (QCQP)) but finding a provably global minimum for large $n$ is likely expensive (NP-hard).
Assuming the big circle is centered at the origin, you want that the small circle centers are more than $d/2$ away from the boundary of the big circle: in other words, the center of the small circles must be within $D/2-d/2$ from the origin. – user7530 Sep 20 '13 at 15:54
The objective minimizes the $y$ values of the small circles, i.e. gravity points in the negative $y$ direction. It then doesn't matter where you center the big circle (notice I am minimizing the value of the y coordinate, not its magnitude.) – user7530 Sep 20 '13 at 18:05