Suppose I have a simple polygon $S$ and an integer $k$. What are some existing approaches for finding the smallest radius $r$ such that I can cover $S$ with $k$ circles of radius $r$? How about if $r$ is fixed, and I want to minimize $k$?
Use the k-center clustering algorithm: see Section 4.2 in http://goo.gl/pLiEO.
One can get 1+eps approximation algorithm using sliding grids.
It is natural to assume the problem is NP-Hard because of the work by Feder and Greene.