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.

  • 1
    $\begingroup$ That is what the sliding grid gives you... $\endgroup$ – Sariel Har-Peled Mar 23 '14 at 17:25
  • $\begingroup$ Thank you for your answer. I am more or less familiar with sliding grids. In the scenario of points it crucially relies on the fact that in each cell of the grid one can solve the covering problem optimally since each disks contains two points on its boundary, plus the number of disks to cover the cell is bounded. Thus one can solve it brute force. But in the setting of a polygon, I do not see how to solve the problem in one grid cell optimally. Would you mind providing some hints on this? $\endgroup$ – 101011 Mar 25 '14 at 0:48
  • $\begingroup$ Sliding grids imply that inside grid cell the solution size is small. Then you need to solve the problem inside each grid cell (usually exactly) using some other algorithm. Here is an alternative way to think about it - sample the polygon very densely, and then solve your problem on the sample... And yes, exact details of how to do this might be pretty painful... So, assume you have a polygon with n edges, and you know the optimal solution is of size k. Do you know how to solve the problem exactly in this case? $\endgroup$ – Sariel Har-Peled Mar 25 '14 at 3:44
  • $\begingroup$ Thank you again. After some more thinking I still don't know how to cover the polygon optimally with k disks, even if I know k. The fact that there is little discrete nature of it makes it seam really hard to me. As for your sampling approach: After sampling, would you then like to cover only the sampled part? Aren't we then running into the problem of wasting a lot of disks to fill in the gaps? $\endgroup$ – 101011 Apr 2 '14 at 21:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Sariel Har-Peled Apr 15 '14 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.