# Distributing fire stations in a circular city

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?

• 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

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))

• 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