1
$\begingroup$

I have a constant area $A$ , and I can mold that area into a regular $n$ -side polygon, where $n\geq 3$. The issue now is how to find the $n$ such that it can contain the most number of circles, each with a constant radius $R$ ?

Edit to clarify the question: the area must be a regular $n$ -side polygon. Sorry for not making this clear

  • 1
    Is the polygon required to be convex? If not, then you can almost always pack $\lfloor A/(\pi R^2) \rfloor$ circles in it by taking $n$ large enough.2010-09-10
  • 2
    Ngu, noting the pattern of your questions lately, I suggest thinking up all the constraints a reasonable (to you) solution may have before you post your question.2010-09-10
  • 0
    @Rahul, it is required to be convex.2010-09-10
  • 3
    Silent editing of questions after they are answered, is discouraged. The original question has been fully and correctly answered, both in the convex and non-convex interpretation. Discussion here: http://meta.math.stackexchange.com/questions/761/bug-in-reputation-system-correct-answer-forces-change-in-question-invalidatin2010-09-10
  • 0
    @T.., is your answer still valid after the edit?2010-09-10

1 Answers 1

5

If $n$ is unconstrained, as it seems to be in the question, then the polygon can be taken to be an $\epsilon$-accurate approximation to the optimal figure, and we can ask directly what that figure (or figures) look like.

  1. If you don't assume the polygon is convex, the answer is trivial, in that you can get as close as desired to a collection of $k$ disjoint circles connected by very thin tubes. In this version of the problem the only constraint is that $A > k \pi R^2$ from which the maximum $k$ is easily determined.

  2. If convexity is required, finding the tightest configuration of circles -- the one whose convex hull is a minimum-area figure containing $k$ or more discs of given size -- is a hard nonlinear optimization problem which is a variant of the classical problem of circle packing (finding the smallest circle enclosing $k$ unit discs). Recent experiments indicate that the optima, even for large $k$, do not have a connectivity pattern approximating the optimal lattice packing.

  3. If the polygon is convex and you are satisfied with an asymptotically optimal solution, start from a hexagonal packing of circles of radius $R$ in the whole plane, and draw a circle of area $A$ that encloses as many of these as possible, then take the convex hull of the circles inside, then approximate the convex hull closely enough by a polygon.

(added: for asymmetry in high density finite packings up to n=348, see http://arxiv.org/abs/1002.0604 and a long series of theory papers by the same authors. Best known packings of small numbers of disks in circles, hexagons, squares, and other shapes are displayed at: http://www2.stetson.edu/~efriedma/packing.html .)

  • 0
    @T, the solution you outline in 2. and 3. don't seem to answer my question at all. My polygon is a regular $n$-side polygon.2010-09-10
  • 2
    I find (2) surprising. Is the last statement in relation to packing unit discs in a *circle*, or in a convex shape of one's choice? If the latter, I would have assumed that arranging the discs in a hexagon would result in the smallest wasted space relative to the arrangement's convex hull.2010-09-10
  • 0
    To put Rahul's question in more familiar terms: so the packing of cells in a beehive is not optimal at all?2010-09-10
  • 0
    If there is a known best packing pattern for the whole plane, of density D, there is no reason why there should not exist finite-area packings of n circles of density D + epsilon(n), where the epsilon is positive but tends to zero for large n, and these finite packings don't have to look like restrictions of the whole-plane pattern. This is the case for n as large as 300 and there is no reason it should not continue as computations are pushed further.2010-09-10
  • 1
    @J. M. : hexagonal packing is *asymptotically* optimal. This is not easy to prove but it can be done, whereas finding the optimal finite packings seems to be an incredibly difficult problem handled by sophisticated computer searches through a nonlinear landscape of many competing near-minima.2010-09-10
  • 0
    @Ngu Soon Hui: the solution I outlined does answer the question that you originally posted, which did not specify a regular n-gon, and which was the only available version of the question at the time I composed the answer. If you change the question please retain the original and mark any modifications as added material ("added", "edit", "update", etc.)2010-09-10
  • 2
    @T..: I agree with your comments in principle, but continue to find this quite unintuitive. Could you provide a reference for the recent experiments you mention, where I could learn more and satisfy myself?2010-09-10
  • 0
    @J.M.: The question I intended to ask was a slightly finer one, that of whether there is a packing of 19 disks with a smaller (convex hull) area than the one illustrated in http://en.wikipedia.org/wiki/Centered_hexagonal_number .2010-09-10
  • 0
    @Rahul: I added some references.2010-09-10
  • 0
    I did some more searching, and it seems G. Wegner proved in a 1986 paper that when n is a centered hexagonal number, "the optimal packing with respect to the convex hull of n disks... indeed has the shape of a regular hexagon" (quote from Dominik Kenn, "Note on a Conjecture of Wegner", http://arxiv.org/abs/0801.1584v1). *Edit:* I posted this before I saw that you had added references.2010-09-10
  • 0
    @Rahul, fixing the number of sides is a different problem, where it is expected (and sometimes proven) for special values of $n$ that the optimal configuration is the standard symmetrical one. For other values of $n$ and a fixed type of boundary, some disorder appears. The circles-in-hexagon packings for n=11, 15, 17 shown at the website above are visibly bent by the boundary, and of the values from 4 to 18 only n=7 (as Wegner proved) and 13 are restrictions of the hexagonal pattern. Conforming to the lattice packing is the exception, not the rule, for the finite configurations.2010-09-10
  • 0
    @T..: Thanks for the references and the explanation. I think my intuition may have been muddled by thinking about a slightly different problem (the one that was originally asked!).2010-09-10
  • 0
    I also found (2) surprising, since the obvious lattice packing is optimal on the infinite plane. But consider that we can arrange 91 circles in a triangle with 13 to a side or in a hexagon with 6 to a side. If I count correctly, there are 144 interior gaps and 36 edge gaps on the triangle (+3 corner gaps), but only 122 interior gaps and 30 edge gaps on the hexagon (+ 6 corner gaps). So a more circular arrangement means less wasted space. I can believe that for large n that are not centered hexagonal numbers, this benefit outweighs the deviation from the lattice packing.2010-09-10
  • 0
    @T.., is your answer still valid after the edit?2010-09-10