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