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$?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.