Cover n points with n disjoint unit disks

629 Views Asked by At

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.

2

There are 2 best solutions below

2
On BEST ANSWER

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
On

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.