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?
2
-
$\begingroup$ Instead of circle, do you mean disk? $\endgroup$– JRNCommented Feb 25, 2013 at 0:51
-
$\begingroup$ Yes, pardon for the imprecision. $\endgroup$– Leo ArrudaCommented Feb 25, 2013 at 15:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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 
-
3$\begingroup$ More from Wikipedia: en.wikipedia.org/wiki/Disk_covering_problem $\endgroup$ Commented Feb 24, 2013 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$ Commented Feb 25, 2013 at 15:55
-
2$\begingroup$ Minimising the distance to the nearest centre is equivalent to covering by smallest disks of equal radius. $\endgroup$ Commented Feb 27, 2013 at 17:50
-
$\begingroup$ I understand it, but could you provide a proof or refer to a place where I can find it? $\endgroup$ Commented Mar 1, 2013 at 4:19