Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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 2

up vote 2 down vote accepted

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.

share|improve this answer
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.