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

-

Consider the square. Cover it by a $N \times N$ grid, for $N=O(k/\epsilon)$. It is easy to prove that any k disks that covers all these points, would cover the whole square after you expand each disk by $\epsilon$ fraction of its radius. As for the polygon, triangulate it, form a grid as above for each triangle (this requires some care, but it is not especially hard). You then get the same guarentee, if you take the union of all these point sets. This is similar to the coreset construction for k-center clustering. –  Sariel Har-Peled Apr 15 '14 at 21:00