<p>You may also want to check out <a href="https://pdfs.semanticscholar.org/056b/67e975ab09fcbece8daa65710cef7d664763.pdf" rel="nofollow noreferrer">https://pdfs.semanticscholar.org/056b/67e975ab09fcbece8daa65710cef7d664763.pdf</a> while the paper describes a method for covering a equilateral triangle the approach is general and is what you are looking for for arbitrary </p>

CC BY-SA 4.0
2020-03-11T03:09:57.683Z
2020-03-11T03:09:57.683Z
kauii8
<p>Use the k-center clustering algorithm: see Section 4.2 in <a href="http://goo.gl/pLiEO" rel="noreferrer">http://goo.gl/pLiEO</a>.</p>

<p>One can get 1+eps approximation algorithm using sliding grids. </p>

<p>It is natural to assume the problem is NP-Hard because of the work by Feder and Greene. </p>

CC BY-SA 3.0
2014-03-23T17:25:24.953Z
That is what the sliding grid gives you...
Sariel Har-Peled
CC BY-SA 3.0
2014-03-25T00:48:26.000Z
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?
101011
CC BY-SA 3.0
2014-03-25T03:44:58.553Z
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?
Sariel Har-Peled
CC BY-SA 3.0
2014-04-02T21:14:42.190Z
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?
101011
CC BY-SA 3.0
2014-04-15T21:00:30.543Z
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
CC BY-SA 3.0
2011-11-04T05:14:52.847Z
2011-11-04T05:14:52.847Z
Sariel Har-Peled
<p>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$?</p>

<cg.comp-geom><planar-graphs><set-cover>
Covering a simple polygon with circles
user771871
# Covering a simple polygon with circles

(Asked by: username_0 on 2011-11-03)

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

**Tags:** cg.comp-geom, planar-graphs, set-cover


---

## 2 answers

### Answer by username_2 on 2011-11-04. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_2**: That is what the sliding grid gives you...  
> **username_3**: 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?  
> **username_2**: 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?  
> **username_3**: 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?  
> **username_2**: 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.  

---

### Answer by username_1 on 2020-03-11. Score: 0

You may also want to check out <https://pdfs.semanticscholar.org/056b/67e975ab09fcbece8daa65710cef7d664763.pdf> while the paper describes a method for covering a equilateral triangle the approach is general and is what you are looking for for arbitrary


---

