2
$\begingroup$

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.

  • 0
    A related question on MathOverflow: http://mathoverflow.net/questions/20558/what-is-the-minimum-n-for-which-there-exist-n-points-in-the-plane-that-cannot-be2011-06-02

2 Answers 2

2

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.

  • 0
    Thanks for the link! :) The paper refer to Veit Elser's paper, which is the best thing available for English speakers, http://arxiv.org/pdf/1101.3468v12011-06-03
1

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.