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

  • $\begingroup$ Thanks for the reply. I just don't get the second contraint, with the modulus of the posiion having to be less than (D-d)^2 / 4. $\endgroup$ – Wasabi Sep 20 '13 at 15:41
  • 1
    $\begingroup$ 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. $\endgroup$ – user7530 Sep 20 '13 at 15:54
  • $\begingroup$ But if the origin is at the center of the big circle, all the q values would also be set around that origin. Wouldn't that make the minimal solution with the small circles around the origin instead of at the "bottom" of the big circle? $\endgroup$ – Wasabi Sep 20 '13 at 17:44
  • $\begingroup$ 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.) $\endgroup$ – user7530 Sep 20 '13 at 18:05
  • $\begingroup$ Yep, thats true. Hadn't noticed that. This looks good. Many thanks. $\endgroup$ – Wasabi Sep 20 '13 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.