# Cover n points with n disjoint unit disks

This is a problem I saw on Peter Winkler's column on communication of the ACM(might be under a pay wall). It is open.

What is the largest $n$, such that you can always cover a given set of $n$ points with $n$ disjoint unit disks?

I believe the current upper bound is $60$.

I would like to know more reference on this problem. Currently I don't even know what field would study problems like this.

-
Discrete Geometry? –  Yuval Filmus Jun 2 '11 at 16:44
Discrete and/or computational geometry are generic labels for this kind of problem. –  yasmar Jun 2 '11 at 16:48
A related question on MathOverflow: mathoverflow.net/questions/20558/… –  Jonas Meyer Jun 2 '11 at 17:35

## 2 Answers

There's a claim of a reduction from 60 to 54. An abstract of Yosuke Okayama, Exclusive covering of point set by unit disks, is available on the web.

-
The full text of the thesis of Yosuke Okayama is available here. It written entirely in Japanese, though. From the abstract I gather that it is the text you're referring to. –  t.b. Jun 3 '11 at 6:02
Thanks for the link! :) The paper refer to Veit Elser's paper, which is the best thing available for English speakers, arxiv.org/pdf/1101.3468v1 –  Chao Xu Jun 3 '11 at 12:26

The 54 result you refer to is available in the proceedings of the Canadian Conference on Computational Geometry. But the result has already been improved slightly. Look for it on arXiv soon.

-