# What is the minimum N for which there exist N points in the plane that cannot be covered by any number of non-overlapping closed unit discs?

This problem was posed in March 2010 at G4G9 in a talk by the Japanese mathematician Hirokazu "Iwahiro" Iwasawa. He claims there is a simple proof that N > 10, though he did not share it with the audience, since it proving it is apparently an enlightening exercise in its own right.

-
Maybe I am missing something, but the result seems obviously false: take a point surrounded by 9 other points in a small circle, then how are you going to have a disk covering the center point without touching the remaining points? If I interpret the problem as saying not every point has to be in a disk, then it seems rather trivially true, because all I need to make sure is every time I add a new disk, it covers at least one point, which is certainly doable. –  John Jiang Apr 6 '10 at 22:44
Perhaps I am misunderstanding this, but I thought MathOverflow was for asking questions to which you do not already know the answer. –  Charles Staats Apr 6 '10 at 22:58
This doesn't yield a very tight bound, but if you fill, say, a 2x2 area densely enough with evenly-spaced points, then no matter how the discs are placed there will always be some points uncovered in the "inverted trefoil" area where three discs come together. –  Josh Jordan Apr 7 '10 at 5:02
@DouglasS.Stones An upper bound appears in this paper: arxiv.org/abs/1101.3468 –  Yoav Kallus Jan 25 '14 at 21:16
I think this question is also interesting in higher dimensions. How does the minimal number $N(d)$ (defined in the obvious way) grow with the dimension $d$? –  Roland Bacher Apr 15 at 8:39

The trick for N = 10 (which I heard from a friend earlier today) is to check that the density of the triangular packing of unit diameter circles is high enough that some translate of this packing must cover all the points.

-

I was told this puzzle last friday by Peter Winkler (who had mentioned that it was told to him by a japanese fellow who is perhaps the one you are referring to).

The solution in the $n \leq 10$ case is to consider the tiling of the plane by unit height hexagons. Inscribe within each of these hexagons a unit circle. This grid of circles has density > 0.90 on the plane, and so if you randomly place this grid on the plane you accordingly have expected number of points covered > 9 (out of the 10), and this implies exists an arrangement that covers 10. (theres a few details missing from this probabilistic method argument, but you get the basic idea).

I believe for the $n>10$ case we have some way of computing an upper bound on the density of a sphere packing on the plane that rules it out in general. (or something to that extent)

-

In the answer to Open problems in Euclidean geometry? , Alexey Ustinov brings into attention to a 2012 article.

Greg Aloupis, Robert A. Hearn, Hirokazu Iwasawa, Ryuhei Uehara, Covering Points with Disjoint Unit Disks, 24th Canadian Conference on Computational Geometry (2012)

The abstract of that article confirms that it's concerned of the same problem, and gives improved bounds.

We consider the following problem. How many points must be placed in the plane so that no collection of disjoint unit disks can cover them? The answer, k, is already known to satisfy 11 ≤ k ≤ 53. Here, we improve the lower bound to 13 and the upper bound to 50. We also provide a set of 45 points that apparently cannot be covered, although this has been determined via computer search.

The article also claims that the lower bound of 11 was published in 2008

-

To bring this problem back to the attention of MO, I'll make a guess. Consider the following set of 13 points: 12 equally spaced on a circle of radius $1+\epsilon$, the 13th at the center of that circle. Can you cover all 13 points with non-overlapping unit disks?

-
–  Josh Jordan Apr 12 '10 at 5:33