Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Assume the circles are actually open disks, otherwise two circles each of area $\frac{1}{4}$ wouldn't fit into the circle of area 1.

This seems like it should be true, thinking about packing density, but I've not been able to find an algorithm that works in all cases.

share|improve this question
1  
I think you mean that two circles each of area $1/4$ wouldn't fit into the circle of area 1. –  Michael Lugo May 11 '10 at 0:46
1  
@Cam, circles of total area 1/2 in a circle of area 1 is the same as circles of total area 1 in a circle of area 2. But it would be nice if the example and the question matched. –  Gerry Myerson May 11 '10 at 2:05
1  
What algorithms / cases did you try? Forgive me if this is stupid, but for instance, when do some of the simpler greedy algorithms fail? e.g. just pack disks around the edge of the big circle until you have to make a second layer, etc. –  j.c. May 11 '10 at 2:08
3  
@jc: Yes, the greedy algorithm (order by size, start on the outside and go around putting them down, start a second layer when needed) fails for specially constructed sequences: Choose some sequence $(d_n)$. The sequence of circles is chosen so that we start a layer with a circle diameter $d_n$, then the whole of this layer, and the first of the next layer is made from circles of diameter $d_{n+1}$. This fails for silly reasons if $d_1>1$ (if the big circle has radius 1), but even ignoring those kinds of cases, I think a rapidly decreasing sequence with large sum will cause trouble. –  Henry Segerman May 11 '10 at 4:51
2  
There are at least a couple of ways to interpret jc's greedy algorithm above. It's not clear to me that there is an obvious counterexample to the greedy algorithm when you interpret it as placing the discs so that they 'spiral in' (as opposed to Henry's interpretation [as I think I understand it] which thinks of the greedy algorithm as filling in concentric annuli). –  Andrew Lobb May 14 '10 at 0:48

5 Answers 5

I have rewritten the post so that the proof is correct.

This problem is a bit hard, but following the Polya dictum, here is the answer to an apparently easier one: yes, if circles are replaced with parallel squares, and moreover, a suitable version of the greedy algorithm works.

Theorem. Let R be an $a$ by $b$ rectangle with $b\leq a\leq 2b.$ Any set of squares of total area at most $ab/2$ can be packed into R. (All rectangles and squares are assumed to be oriented parallel to the coordinate axes throughout.)

Corollary 1. A finite set of squares of total area 1 can be packed into a square of area 2.

Corollary 2. A finite set of circles of total area 1 can be packed into a circle of area 4.

Proof of Corollary 2. Replace each circle of diameter $d$ with a square of size $d$. Pack the squares into a square of double their total area, then circumscribe a circle C around it. The inscribed circles of the small squares have given radii, disjoint interiors, and the area of C is four times the total area of the given circles. $\square$

Proof of Theorem. The proof is by induction on the number of squares and uses the Packing Lemma below. Suppose that the largest square has size $c.$ Since $c^2\leq ab/2\leq b^2,$ we get $c\leq b.$ Split the rectangle R into two rectangles R' and R'' of the same height $b$ and of widths $c$ and $a-c$.

Case 1. If $c\leq a-b/2$ then the dimensions of the right rectangle R'' satisfy the conditions of the theorem, because $b/2\leq a-c\leq 2b.$ By the Packing Lemma, at least half the area of the left rectangle R' can be packed, starting with the $c$ square. The remaining squares are fewer in number and constitute at most half the area of R''. By the inductive assumption, they can be packed into R''.

Case 2. If $c\geq a-b/2$ then $b\geq 2(a-c)$ and R'' contains a subrectangle R''' of height $2(a-c)$ and width $a-c$, to which the theorem applies. Pack the $c$ square into R'. Since $c^2+(a-c)^2\geq a^2/2\geq ab/2,$ the remaining squares have total area at most $(a-c)^2$ and can be packed into R''' by the inductive assumption. $\square$

Packing Lemma. Let R be a $c$ by $b$ rectangle, $c\leq b$, and F be a finite set of squares with the total area at least half the area of R and the largest square of size $c$. Then a subset of F containing the $c$ square can be packed into R so that it covers at least half the area of R.

Proof. Induction in the number of squares in F. Cut the rectangle R into a sequence of horizontal strips of width $c$, starting with the $c$ square at the top. The height of each subsequent strip is the size of the largest unused square, which is placed at the left end. By the inductive assumption, at least half of the strip, area-wise, can be packed with squares from F. Continue the process until the height of the remaining part of R ("the bottom strip") becomes less than $c$, and hence its area less than $c^2.$ At this point at least half of the area of the intermediate strips has been covered, as well as the larger of the areas of the top and the bottom strip, so that at least half of R has been covered. $\square$

Comment: In the initial post, I said that the Packing Lemma easily implied the result for packing the square: order the squares by size and successively apply the lemma to pack vertical columns whose widths are determined by the largest square not yet packed, starting with the largest. While that argument had virtues of simplicity and presentability, it had an unfortunate drawback of being invalid. The columns are getting skinnier, so it may well happen that passing to the next column, the largest remaining square is too wide to fit, even though its area is a tiny proportion of the remaining area. Specific example: if one attempts to pack the squares of sizes 1/2, 1/3, 1/6+$\epsilon$, 1/6+$\epsilon$, 1/6 into the square of size $2\sqrt{2}/3+\epsilon<1$ following the naive algorithm then the first column has width 1/2 and contains the 1/2 square, the second column has width 1/3 and contains the next 3 squares (covering at least half the area in both cases), which leaves a narrow vertical strip of width less than 1/6 that cannot accommodate the remaining 1/6 square. By controlling the distortion (the ratio of width and height), we get a more natural result.

share|improve this answer
    
@Victor: I am convinced. But since I voted on your answer already when you posted it, I can't put you higher. In any case, I find this "democratic" voting very inadequate. –  Wadim Zudilin May 16 '10 at 1:20
2  
Hi Wadim, I am sorry that you felt that way about people's reaction to your answer - I wish you'd left it there, it certainly looked very interesting to me! FWIW, someone downrated my post, too! Having spent last several hours chasing references, I've found out that much is known about these kinds of problems. Apparently, there is an online algorithm for squares with the same constant 2, which implies constant 4 for circles. ("Online" means that squares are given in a sequence, with the total area fixed ahead of time, and must be packed sequentially with no later changes allowed). –  Victor Protsak May 16 '10 at 2:21
1  
Victor, I just feel sad about the whole answering story for this question. –  Wadim Zudilin May 16 '10 at 2:53
    
Following the link in Apery's question, I found an interesting "circle" of packing problems, Jung's and Borsuk's problem. The results are nice by themselves (and maybe not well related to the OP, my findings include dx.doi.org/10.2307/2031795 and dx.doi.org/10.1017/S0305004100032849). But is it possible to prove a similar lemma for right $n$-gons instead of squares, under the same assumption of equal orientation (so, they are congruent)? If yes... (I don't need to continue). –  Wadim Zudilin Jun 8 '10 at 7:05
    
Victor -- sorry to bother you -- but I can't follow the proof of the Packing Lemma. This came up in some undergraduate maths puzzle-solving group here in London. The trivial comments are that you talk about the "top" and the "width" and "horizontal strips" etc etc without ever explaining what the orientation of everything is. But I think I can guess my way around these things. The thing that really bothers me though is the application of the inductive hypothesis. You say "By the inductive assumption, at least half of the strip, area-wise, can be packed with squares from F". But I am... –  Kevin Buzzard Feb 10 '12 at 20:47

It's still not a yes-or-no answer to your question, but it seems to be true that a collection of circles with area 1/9 can always fit into a circle of area 1. Or, more strongly, if the circles are placed largest-first, then no matter how the larger circles are placed (by a malicious adversary trying to prevent the packing from succeeding) there will always be room for each circle to be placed.

Proof sketch: as the circles are placed, maintain an "exclusion zone" where centers of new circles cannot go without potentially conflicting with existing circles. Initially, the exclusion zone covers the outer 1/3 of the radius of the area-1 circle, leaving 4/9 of its area free; with this initial exclusion zone, a circle with area at most 1/9 can have its center anywhere in the free area and not fall outside the boundary of the area-1 circle.

Then, when placing any circle, add to the exclusion zone a circular area with twice its radius; smaller circles whose centers are outside this zone cannot conflict with the placed circle.

If the total area of all circles is at most 1/9, then the total area of the exclusion zones formed in this way will always be less than 1, and there will always be a safe place for the center of the next circle to go.

share|improve this answer
    
This is not a solution; the sketch cannot be converted to a proof, and in any case $1/9$ is too less compared to $1/2$. Seeing that this nonsolution is higher that my unsuccessful attempt (which got score 4 = +6 -2, the people are not critical but cruel!) I have decide to delete it. –  Wadim Zudilin May 16 '10 at 1:17
1  
Dear Wadim Zudilin, I regret your decision. Your post was very beautiful and inspiring and this is one of the main points of interesting maths (and I disagree strongly with people who voted your post down). –  Roland Bacher May 18 '10 at 9:04

After passions calmed down, I can put back my old unsuccessful attempt. At least I was quite enthusiastic at that time about the problem, until I have got downvotes and seen some vague ideas of others (they are still here) as answers.

Post as it was on May 12, 2010. Consider 3 circles of radii $r_1=r$, $r_2=2r$ and $r_3=3r$, where $r=1/(2\sqrt{7\pi})$, so that their total area $s$ is $$ s=\pi(r_1^2+r_2^2+r_3^2)=\frac12. $$

Descartes' theorem asserts that if three circles of radii $r_1$, $r_2$ and $r_3$ are pairwise externally tangent to each other and circumscribed by the circle of radius $R$, then $$ \frac1R=2\sqrt{\frac1{r_1r_2}+\frac1{r_2r_3}+\frac1{r_3r_1}} -\biggl(\frac1{r_1}+\frac1{r_2}+\frac1{r_3}\biggr). $$ In our case we find from this formula that $$ R=\frac3{\sqrt{7\pi}}, $$ so that the area $S$ of the circumscribing circle is $$ S=\pi R^2=\frac97>1. $$ This implies that the three given circles of total area $1/2$ cannot be put inside a circle of total area 1 without intersections.

Edit. I have to agree that my geometric intuition is too weak to notify an obvious non-applicability of Decartes' theorem. As Tony mentions in his comment, one can fit these three circles in a circle of radius $r_2+r_3$, and the circle of radius $r_1$ fits in one of the gaps, without touching the enclosing circle.

Without trying to correct the above solution I indicate another choice: $r_1=0.99q$, $r_2=r_3=2q$, where $q$ is chosen in such a way that the total area is again $1/2$. Decartes' theorem produces the circumscribing circle of area $>1.008$. There is still an option to put two large circles along a diameter of circle of total area 1 and see whether there is a room for the smaller one. This definitely means that more geometry is involved...

Final edit (hopefully). As Roland mentions, the three circles again fit a circle of radius $r_2+r_3$. After the two large equal circles are inscribed, there is a room for another circle of radius $2r_2/3$ (well, one can still have the space for the other of radius $2r_3/3$, but I do not care of more than 3 circles inscribed). The corresponding geometric picture involves the right triangles with sides $1$, $4/3$, and $5/3$, a nice appearance of the Pythagorean triple $3^2+4^2=5^2$.

Is it true that this ($r_1=2/3$, $r_2=r_3=1$, total area $s=22\pi/9$) is the worth case of inscribing 3 circles into the circle of radius $R=2$ (area $S=4\pi$)? The quality of this inscription is $S/s=18/11$. In other words, can we replace areas $1/2$ and $1$ in the original problem by $11/18$ and $1$ respectively, if at least three circles are inscribed?

I have to apologize for my unsuccessful attempt. You still have a chance to enjoy the beauty and difficulty of the original problem. I thank Tony and Roland for pointing out my mistakes in geometry.

share|improve this answer
    
Nice! (if correct:) If I weren't so obsessed with polishing it, at least I could have posted my answer (positive, but to a different question) first. –  Victor Protsak May 12 '10 at 10:32
5  
I think you can fit these three circles in a circle of radius r2 + r3. The circle of radius r1 fits in one of the gaps, without touching the enclosing cirlce, so Descartes' theorem doesn't apply. –  TonyK May 12 '10 at 11:08
    
@Victor: I spent quite a long time trying to construct an explicit counter example. I was sure from the beginning that the answer is negative. I'm surprised to see that our solutions "crossed" in time. Please keep your answer because it shows how different are two similar situations. –  Wadim Zudilin May 12 '10 at 11:09
    
If your Wikipedia link is correct, you have a sign wrong in your statement of Descartes' theorem: the minus should be a plus. –  TonyK May 12 '10 at 11:38
2  
Given two tangent circles of equal radii $r$ inscribed in a circle of radius $2$, one can insert another (in fact two) circle of radius $2r/3$ which is tangent to the three previous ones. –  Roland Bacher May 12 '10 at 11:45

This is not at all a complete answer but a remark which can be improved. It is a completely rewritten and replaces bullshit (explaining the first comments.)

Suppose the answer to Segerman's question is no. There exists thus a counterexample given by a decreasing sequence $r_1\geq \dots \geq r_n$ of radii such that $\sum_{i=1}^n r_i^2=1/2$ and one can not fit $n$ circles with radii $r_1,\dots,r_n$ into a circle $C_1$ of radius $1$. Suppose $n$ is the smallest integer for which a counterexample exists. Then $r_1<2/3$. Indeed, the area $\pi(1/2-r_1^2)$ of the discs of radii $r_2,\dots,r_n$ is at most half the area $\pi(1-\rho_1)^2$ of the largest disc $C'$ which fits together with the disc $C_1$ of radius $r_1$ into $C$. Since $n$ is minimal, the $(n-1)$ circles of radii $r_2,\dots,r_n$ can be packed into $C'$.

This kind of argument can be improved (pack the circles of radii $r_2,\dots$ into more than one circle of suitable radii which fit into $C$ together with $ C_1$) in order to lower the upper bound on the largest radius of a minimal counterexample.

I guess one can use a packing argument showing that a solution always exists if the largest radius is small enough.

These two bounds can perhaps be made to met (but I fear that the involved combinatorics are quite messy).

Let me make the argument for small radii a little bit more (but not entirely, I agree that some more work is needed) rigorous. (This is probably similar to the argument suggested by fedja (see comment below), I admit that I do not quite understand the details).

Supposing the total area of all discs of radius $\leq \epsilon$ exceeds $2\pi \epsilon$, look at the annulus of width $\epsilon$ and outer radius $1$ inside the large disc, supposed to be of radius $1$. If $\epsilon$ is very small, such an annulus looks locally like a strip delimited by two parallel lines at distance $\epsilon$. I have thus to prove that given a collection of radii $\leq 1/2$, I can cover more than half of the area of a very long strip delimited by two parallel lines at distance $1$.

If all discs have equal radius, then I can cover asymptotically a proportion of at least $\pi/4\sim .7854$ of the strip (the least favorable case corresponds to a collection of discs all of maximal radius $1/2$). The general case should be better but is harder to analyze. I claim however that this analysis can be made. Indeed, up to subdividing the strip into smaller substrips, we can assume that all radii are $>1/4$ and we have then a fairly small number of combinatorial situations to consider. We can thus compute the worst case.

share|improve this answer
    
@roland-bacher: Thanks for your kind words above. Yes, this trick should have a combinatorial interpretation. It looks like if $4R^2/9\le r_1^2+\dots+r_n^2\le R^2/2$, then one can place circles of radii $r_1,\dots,r_n$ inside the circle of radius $R$ in such a way that there is a room inside the large circle for one circle of radius $\sqrt{R^2-2(r_1^2+\dots+r_n^2)}$. You show this for $n=1$ and last couple of hours I spent on $n=2$: it works but the solution is too complicated. –  Wadim Zudilin May 20 '10 at 11:14
    
I don't buy "one can use a packing argument showing that a solution always exists if the largest radius is small enough" claim. The best you can reasonably hope for is a simplified solution if the ratio of the largest to the smallest radius is assumed bounded by an a priori constant, which is a rather strong condition. –  Victor Protsak May 20 '10 at 11:29
1  
If all radii are small enough, the greedy algorithm (arrange disks in the decreasing order and pack them so that each next circle touches either at least two of the previously packed one or at least one of the previously packed one and the boundary circle) does the job, the reason being that if a disk D of radius $r$ touches two bigger disks $F,G$, then the area of $2D\setminus (2F\cup 2G)$ is not greater than t times the area of $D$ with t < 2, so this case is trivial. The troublesome disks are those with radii greater than 1/20 or so. If you can pack those, you can pack the rest. –  fedja May 20 '10 at 20:49

After weeks of sweating through computations without success, I think I have an auxillary result which I can use to tackle the problem posted above. However, the path to the conclusion is so surprising that I invite verification, in particular to point out any show-stopper mistake that may or may not be lurking.

The auxillary result involves a region that is the "suitcase" circle with a segment removed. Let C be a disk of radius 1, and draw a chord of C which has distance 1/2 from the center of C. Let D be that part of C (including the chord itself) that is on the same side of the chord as the center of C, so D is a disk with a segment chopped off so that the area of D is less than 5/6 the area of C. Let F and G be two closed disks with unequal radii whose areas sum to half the area of C.

Result: F and G pack inside D.

Note that if F and G have the same radius, they will not pack inside D for the same reason they won't pack inside C: they have to share a point which is the circle center.

The proof of the result involves placing F and G so that they touch the chord and otherwise are as far apart inside D as possible. The analogous problem for packing inside C involves placing F and G inside C so that the centers of F, G, and C are on the same line and F and G are as far apart as possible, then use the area sum condition to show the radii of F and of G sum to less than 1, and so they can be pushed together just enough to remain disjoint and keep away from the region boundary.

For the result about D, I orient the coordinates to have the chord parallel to the x axis, and then I show that the x coordinates of the centers of F and G are greater than distance 1 apart. It took me weeks to realize that was what was needed to be shown. Even so, the algebra involved led to a surprise, which I want someone else to confirm or deny.

Now for the algebraic verification. Let $0 \leq s \lt 1/2 \lt r \leq \sqrt{1/2}$ where $s$ and $r$ are the lengths of the radii of F and G. The area sum condition yields $r^2 + s^2 = 1/2$, and the inequality to be shown is inequality (A): $\sqrt{3/4 - r} + \sqrt{3/4 - s} \gt 1$. Since this inequality on the x coordinates of the centers of F and G imply that F and G are disjoint, inequality (A) will yield the result.

There may be a slick analytic way to show (A), but I use repeated squaring and rearrangments to yield a quartic polynomial in $r$. I start by writing $s$ as $\sqrt{1/2 - r^2}$ and isolate the radical with $s$ on one side, and square both sides. I end up with an inequality to prove that has $\sqrt{1/2 - r^2}$ as a subexpression, and so I isolate the summand containing that subexpression on one side and square again.

I collect and rearrange and square again to get the following inequality to be shown: $49/4 - 42r + 50r^2 - 24r^3 + 4r^4 \gt (1 - 2r + r^2)(12 - 16r)$. I then collect terms and decide to factor out a term of $(r - 1/2)$ in hopes of getting an easier polynomial to handle to show that it is positive for $r$ in the range given above. I know the relations above yield 0 when $r$ is $1/2$, so it seems like a nice simplification.

The surprise comes when I find out the above inequality is equivalent to (B): $4(r - 1/2)^4 \gt 0$. I was not expecting that at all! If I have it right, then the result is proved, and I can move on after weeks of fruitless labor involving delta and epsilons and sketches that had no $r$'s or $s$'s. Can someone rederive or otherwise prove inequality A above? Even better, can someone tell me how I could know inequality B was coming?

Gerhard "Surprised After All These Weeks" Paseman, 2012.05.07

share|improve this answer
    
I can reconstruct your derivation. I can't explain (B). I'm intrigued to see how this will build into an arbitrary group of discs. –  Ed Wynn Jun 8 '12 at 17:55
    
The hope is that I will be able to pack enough disks into D that I can show either all the disks pack into D, or, for some large enough percentage p, disks containing at least p of the area pack into D and the rest pack into C - D. Gerhard "Thanks For Verifying The Derivation" Paseman, 2012.06.08 –  Gerhard Paseman Jun 9 '12 at 0:30

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.