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.
You may also want to check out https://pdfs.semanticscholar.org/056b/67e975ab09fcbece8daa65710cef7d664763.pdf while the paper describes a method for covering a equilateral triangle the approach is general and is what you are looking for for arbitrary