# filling a square with circles

• Apr 22nd 2010, 09:06 AM
becko
filling a square with circles
I found this problem on Charles Chapman book, Real Mathematical Analysis:

Given epsilon>0, prove that finitely many disjoint circles can be draw inside the unit square so that the total area of the discs exceeds 1 - epsilon.

The first idea that comes to my mind is to try to fill the square with ever smaller disks of the same size. But the problem with this approach is that the total area covered by the disks is always the same! It will not change as you decrease the size of the disks.

So all the disks cannot be of the same size. I need a new strategy. Any ideas?

By the way, this is all in the plane. Maybe it can be extended to more dimensions, but I will be satisfied with a solution in 2D.
• Apr 22nd 2010, 09:36 AM
southprkfan1
Quote:

Originally Posted by becko
I found this problem on Charles Chapman book, Real Mathematical Analysis:

Given epsilon>0, prove that finitely many disjoint circles can be draw inside the unit square so that the total area of the discs exceeds 1 - epsilon.

The first idea that comes to my mind is to try to fill the square with ever smaller disks of the same size. But the problem with this approach is that the total area covered by the disks is always the same! It will not change as you decrease the size of the disks.

So all the disks cannot be of the same size. I need a new strategy. Any ideas?

By the way, this is all in the plane. Maybe it can be extended to more dimensions, but I will be satisfied with a solution in 2D.

Is this a measure theory question? Are you familiar with Vitali covering lemma? If not, then ignore the rest of what I'm about to say.

Let S be the unit square. Let T be a square contained in S such that the area of T is 1 - $\frac{\epsilon}{2}$

Let V = {closed balls $B \in S$ ; such that $B \cap T \neq \emptyset$}

Then V is a Vitali cover of T.

By the Vitali Covering Lemma, for all $\delta > 0$there exists countably many disjoint balls $B_i \in V$ such that if $U = \bigcup(B_i)$, then m(T\U) = 0 and $m(U) \leq m(T) + \delta$.

Thus, it can be showed we can find finitely many of the balls $B_i$ such that if W is there union then m(T\W) < $\frac{\epsilon}{2}$.

• Apr 22nd 2010, 11:32 AM
becko
Thanks. But I'm looking for something a little more elementary than that, just using basic analysis, limits, sequences, exhaustion, things like that. The problem is from the first chapter of the book.

Vitali is only mentioned on the 6th chapter on Lebesgue integration. So I'm sure a more elementary answer can be given.
• Apr 22nd 2010, 11:44 AM
southprkfan1
Quote:

Originally Posted by becko
Thanks. But I'm looking for something a little more elementary than that, just using basic analysis, limits, sequences, exhaustion, things like that. The problem is from the first chapter of the book.

Vitali is only mentioned on the 6th chapter on Lebesgue integration. So I'm sure a more elementary answer can be given.

No Problem, I had a feeling.

I wold think the answer has to to with breaking the square up into smaller and and smaller squares, each of which contains its own circle, and you could keep doing this ... If I can better formalize it I will.

On another unrelated, but possibly interesting (only to me) note. The author of that book, Pugh, was once my prof.
• Apr 22nd 2010, 11:01 PM
becko
I think that breaking the square into smaller squares, each of which contains its own circle, will lead you astray, as it did me. If each square contains its circle and doesnt intersect other circles, then the ratio of area covered to the area of the square remains fixed, no matter what size you make the small squares.

We need a different strategy. A circle must be allowed to penetrate into the squares that circumscribe neighboring circles.

By the way, I think I saw somewhere that the circles of someone (name of important person here) do this. I just can't remember where I saw this, and what was the name of the mathematician.

So you studied with Pugh. Can you share something about him? Was he a good teacher in person? I think the book is pretty good.
• Apr 23rd 2010, 03:51 AM
southprkfan1
Quote:

Originally Posted by becko
I think that breaking the square into smaller squares, each of which contains its own circle, will lead you astray, as it did me. If each square contains its circle and doesnt intersect other circles, then the ratio of area covered to the area of the square remains fixed, no matter what size you make the small squares.

We need a different strategy. A circle must be allowed to penetrate into the squares that circumscribe neighboring circles.

By the way, I think I saw somewhere that the circles of someone (name of important person here) do this. I just can't remember where I saw this, and what was the name of the mathematician.

So you studied with Pugh. Can you share something about him? Was he a good teacher in person? I think the book is pretty good.

OK prof. I hardly remember to be honest

I don't think I was clear in what I said. I meant something like start with the biggest possible circle in the square. Then look at the uncovered regionS and break them down in the largest squares possible and put circles in them and keep doing that....
• Apr 23rd 2010, 09:20 AM
Laurent
Quote:

Originally Posted by becko
By the way, I think I saw somewhere that the circles of someone (name of important person here) do this. I just can't remember where I saw this, and what was the name of the mathematician.

You must be referring to Apollonian packings of circles. You can also do it in a square: first the inscribed circle and then Apollonian packings in each of the four corners (there is a figure in Falconer, "Techniques in fractal geometry", p.55 (if your library has it) but no proof).

It is true that the measure of the complement goes down to 0 as we add circles. This implies your result: choose a subset of discs whose complement has measure less than $\epsilon/2$. Then reduce the radius of the $n$-th circle ( $n\geq 1$) so that its area is reduced by $\frac{\epsilon}{2^{n+1}}$ (or delete the circle if this is larger than the initial area). Then the circles become disjoint, and the area of their complement is less than $\frac{\epsilon}{2}+\sum_{n\geq 1}\frac{\epsilon}{2^{n+1}}=\epsilon$.

It is however not obvious that the measure of the complement goes down to 0 as the number of circles increases. This doesn't follow from a "general argument". You can find a very nice proof here, but I don't think your book expects you to think of that. So I don't know what it may be expecting.

Another proof can be derived from the proof that the Hausdorff dimension of the complement is strictly less than 2, which you can find in Falconer, "The geometry of fractal sets" p 125-131 (it follows a paper by Hirst) but this proof is more advanced (and much more computational).
• Apr 26th 2010, 08:55 PM
becko
I think I know a solution now (got the idea here: Art of Problem Solving &bull; View topic - filling a square with circles). It goes like this:

(I assume that squares can cover any area as tightly as needed by making the squares smaller and more numerous. After this proof, the same follows for circles.)

Let $s$ be the supremum of the areas that can be covered by finitely many disjoint discs inside the unit square. Take $\tau >0$ and let $A$ be a packing of disjoint discs inside the unit square whose total area is $s-\tau$. The complement of this packing can be nearly filled with finitely many disjoint squares, leaving an area $\delta$ uncovered, which can be made as small as we want by making the squares smaller. Inside each of these squares we can repeat the packing $A$. Then the total area covered by the circles will be:

$s-\tau +(s-\tau )(1-s+\tau -\delta )$

(EDIT: fixed this. The -delta was outside the parenthesis, but it should be inside)

If we make $\tau \rightarrow 0$ and $\delta \rightarrow 0$, the result should be the supremum $s$, so we have the equation:

$s+s(1-s)=s$

which implies $s=1$. This completes the proof.
• Apr 27th 2010, 12:12 AM
Laurent
Quote:

Originally Posted by becko
I think I know a solution now (got the idea here: Art of Problem Solving &bull; View topic - filling a square with circles). It goes like this:

Nice proof. Matching this idea very closely gives: for any $\varepsilon>0,\delta>0$, we have $s\geq s-\varepsilon+(1-s-\delta)c$ where $c=\frac{\pi}{4}$ is the area of the disc inscribed in a unit square (or the area of any disc(s) in this square) (Indeed, an area $A_0\geq s-\varepsilon$ is filled with circles initially, and an area $A_1\geq(1-A_0-\delta)c$ of the complement as well, hence a total area $A_0+A_1\geq s-\varepsilon+(1-A_0-\delta)c\geq s-\varepsilon+(1-s-\delta)c$ since $A_0\leq s$, and $A_0+A_1\leq s$ by definition of $s$). Letting $\varepsilon,\delta\to 0$, we get $s\geq s+(1-s)c$, hence $(1-s)c=0$ and finally $s=1$.