# Covering the plane with disks

How to prove that it is impossible to cover the plane with disks? /The disks are closed disks and two disks can meet (at most) at only one point (obviously on the border)./ Thank you very much in advance! Edit: The disks are not of fixed radius.

-
Are the disks of fixed radius? –  Ｊ. Ｍ. Apr 30 '11 at 15:22
Then the Apollonian gasket should be of interest... –  Ｊ. Ｍ. Apr 30 '11 at 15:39
@J. M., but the gasket doesn't cover the whole plane, right? –  Alon Amit Apr 30 '11 at 15:52
No, it's impossible to cover the plane with the Apollonian gasket nor, I believe, in any other way. I'm still trying to figure out why... –  Alon Amit Apr 30 '11 at 15:58
On the very same link post by J.M.:"The points which are never inside a circle form a set of measure 0 having fractal dimension approximately 1.3058". –  Jiangwei Xue Apr 30 '11 at 16:01

Here's a somewhat more elementary proof (no Baire property :-) that explicitly constructs a point not covered by a given set of (almost) non-overlapping disks.

By fixing an enumeration of the points with rational coordinates, we can enumerate the disks in the order in which we encounter them when enumerating these points. (If two disks touch at such a point, we can enumerate them in lexical order of their centres.) So there are countably many disks, and hence countably many pairs of disks, and hence countably many touching points of disks, and also countably many top and bottom points of disks (points with extremal $y$ coordinates).

Pick some point $p_1$ in the plane that has a $y$-coordinate different from all touching points, top points and bottom points. Proceed to cover the plane with the disks according to the enumeration until $p_1$ gets covered. Then move out of the covering disk in the positive $x$ direction to an as yet uncovered point $p_2$ just beyond its boundary with no covered points in between. This is possible, since the point you hit on the boundary is not a touching point, and only finitely many disks have been covered, so there must be a finite gap beyond the boundary. Now continue to cover disks according to the enumeration until $p_2$ gets covered, and again move out of the covering disk to an as yet uncovered point $p_3$ just beyond the boundary, but this time moving in the negative $x$ direction. Continue alternating between moving right and moving left. The result is an alternating series of moves by strictly decreasing distances (since we never move back past earlier, now covered points), which converges to some point to the right of all odd-numbered points and to the left of all even-numbered points. The limit point can't be in the interior of a disk, since the points are eventually outside each disk. But to be on the boundary of a disk, it would have to be a top or bottom point, since these are the only ones that you can alternatingly jump to the left and right of as you converge to them. But the limit point has the $y$ coordinate at which we started, and that was by assumption not the $y$ coordinate of any top or bottom point. Thus the limit point is neither in the interior nor on the boundary of any of the disks.

I tried to avoid having to make the argument about top or bottom points by using the Dirichlet test with three directions at angles of $120^\circ$ (inspired by the Apollonian gasket) instead of the alternating series test, but I couldn't make that work -- let me know if you can.

For those interested in whether a proof requires the axiom of choice: This one doesn't since we can make all choices explicit. The lexical order that decides which of two points touching at a point with rational coordinates to enumerate first is explicit; the point "just beyond the boundary" can be the first as yet uncovered point at a distance $2^{-n}$ from the boundary with no covered points in between; and we only need a single choice of an initial point and of an enumeration of the points with rational coordinates.

-
Thanks for this. I was also looking for an argument that avoids Baire category. –  Byron Schmuland May 2 '11 at 17:16
Thank you for your answer. To tell the truth, the property of Baire horrified me a little bit. Naturally I am really grateful for Plop's quick answer as well. –  benny May 2 '11 at 18:40

Assume $\mathbb{R}^2 = \cup_{n \geq 0} \bar{D}(x_n,r_n)$, and that the $D(x_n,r_n)$ are disjoint. Then $X = \cup_{n \geq 0} C(x_n,r_n) = \mathbb{R}^{2} \setminus \cup_{n \geq 0} D(x_n,r_n)$ is a closed subset of $\mathbb{R}^2$, in particular it is a complete metric space. $X$ being the countable union of closed subsets, by Baire's property there is a circle $C(x_n,r_n)$ which contains a non-empty open subset of $X$, i.e. there is a point $y \in C(x_n,r_n)$ and an $\epsilon > 0$ such that $X \cap D(y,\epsilon) \subset C(x_n,r_n)$.

Let's take a point $z \in D(y,\epsilon) \setminus \bar{D}(x_n,r_n)$ (time to draw a picture!). Then $z \in \bar{D}(x_m,r_m)$ for some $m \neq n$. So $C(x_m,r_m)$ is disjoint from $D(y,\epsilon)$, which implies that either $D(y,\epsilon) \subset \bar{D}(x_m,r_m)$, or $D(y,\epsilon) \cap \bar{D}(x_m,r_m) = \emptyset$. But $z \in D(y,\epsilon) \cap \bar{D}(x_m,r_m)$, so we get that $D(y,\epsilon) \subset \bar{D}(x_m,r_m)$, but then $D(y,\epsilon) \cap \bar{D}(x_n,r_n) \subset \bar{D}(x_n,r_n) \cap \bar{D}(x_m,r_m)$ so the latter has more than one point, which is a contradiction.

-
Are you assuming as obvious that the set of disks would have to be countable? (This follows because each of the disjoint disks contains a rational.) –  joriki Apr 30 '11 at 18:24
Oh yes thanks, I forgot that point, and also that the radii have to be positive. –  Plop Apr 30 '11 at 18:31