Covering a simple polygon with circles 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.