3
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
5
  • $\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, 2013 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, 2013 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, 2013 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, 2013 at 18:05
  • $\begingroup$ Yep, thats true. Hadn't noticed that. This looks good. Many thanks. $\endgroup$
    – Wasabi
    Sep 20, 2013 at 18:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .