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?

  • $\begingroup$ Instead of circle, do you mean disk? $\endgroup$ – Joel Reyes Noche Feb 25 '13 at 0:51
  • $\begingroup$ Yes, pardon for the imprecision. $\endgroup$ – Leo Arruda Feb 25 '13 at 15:27

This is the (finite) covering problem in the plane. According to Böröczky'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 (source))

  • 3
    $\begingroup$ More from Wikipedia: en.wikipedia.org/wiki/Disk_covering_problem $\endgroup$ – Yoav Kallus Feb 24 '13 at 23:28
  • $\begingroup$ 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? $\endgroup$ – Leo Arruda Feb 25 '13 at 15:55
  • 2
    $\begingroup$ Minimising the distance to the nearest centre is equivalent to covering by smallest disks of equal radius. $\endgroup$ – Ben Barber Feb 27 '13 at 17:50
  • $\begingroup$ I understand it, but could you provide a proof or refer to a place where I can find it? $\endgroup$ – Leo Arruda Mar 1 '13 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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