Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a constant area $A$ , and I can mold that area into a regular $n$ -side polygon, where $n>=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

share|improve this question
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. –  Rahul Sep 10 '10 at 3:08
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. –  J. M. Sep 10 '10 at 3:16
    
@Rahul, it is required to be convex. –  Graviton Sep 10 '10 at 4:16
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: meta.math.stackexchange.com/questions/761/… –  T.. Sep 10 '10 at 6:41
    
@T.., is your answer still valid after the edit? –  Graviton Sep 10 '10 at 15:52
add comment

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
    
@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. –  Graviton Sep 10 '10 at 4:21
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. –  Rahul Sep 10 '10 at 4:32
    
To put Rahul's question in more familiar terms: so the packing of cells in a beehive is not optimal at all? –  J. M. Sep 10 '10 at 5:25
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. –  T.. Sep 10 '10 at 6:31
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? –  Rahul Sep 10 '10 at 6:58
show 9 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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