Covering a simple polygon with circles

Question

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$?

Answer 1

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.