Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How to distribute k points inside a disc so to minimize the distance of any point inside the disc to the closest of the k points? Does this problem have a name? Is the solution a famous sequence of geometric graphs?

share|improve this question
    
Instead of circle, do you mean disk? –  Joel Reyes Noche Feb 25 '13 at 0:51
    
Yes, pardon for the imprecision. –  Leo Arruda Feb 25 '13 at 15:27
add comment

1 Answer

This is the (finite) covering problem in the plane. According to Boroczky's book "Finite packing and covering", the answer is only known (provably) up to $k = 10$, due to the work of K. Bezdek and G. Fejes Toth. I don't know if the solutions are a famous sequence of geometric graphs.
           (Image from MathWorld added by J.O'Rourke)

share|improve this answer
3  
More from Wikipedia: en.wikipedia.org/wiki/Disk_covering_problem –  Yoav Kallus Feb 24 '13 at 23:28
    
Thanks a lot Joseph, this seems to be a good solution but I'm not convinced same radius circles are always the best solution, do you think this can be/has been shown? –  Leo Arruda Feb 25 '13 at 15:55
    
Minimising the distance to the nearest centre is equivalent to covering by smallest disks of equal radius. –  Ben Barber Feb 27 '13 at 17:50
    
I understand it, but could you provide a proof or refer to a place where I can find it? –  Leo Arruda Mar 1 '13 at 4:19
add comment

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.