<p>We decomposed a simple polygon into many small regions. Then we estimated a visibility polygon of a point by a subset of the small regions. Now I need the minimum set of visibility polygons that can cover all the small regions, the whole polygon. This can be seen as an instance of the Set Cover problem. However, I need an easier approach. As we deal with visibility polygons inside a simple polygon there must be an easier way than a general instance of the Set Cover problem.</p>

CC BY-SA 4.0
2021-09-16T13:13:41.540Z
for reference, the problem is NP-hard, but it looks like there is a polytime constant-factor approximation algorithm, and maybe a PTAS [https://en.wikipedia.org/wiki/Art_gallery_problem].  If for some reason you need to do it via set cover, properly formulated, it may be a special case of geometric set cover, which is somewhat easier than general set cover [https://en.wikipedia.org/wiki/Geometric_set_cover_problem].
Neal Young
CC BY-SA 4.0
2021-09-16T13:50:30.843Z
The wikipedia page on geometric set cover is out of date. It does not refer to the large amount of progress made in the last decade or so.
Chandra Chekuri
CC BY-SA 4.0
2021-09-16T13:54:24.683Z
Thank you. A PTAS algorithm for the general Art Gallery problem cannot be provided and constant approximation factor provided by Gosh in arXiv is not correct. As far as I know, a constant factor approximation algorithm for the Art Gallery problem is still open.
Arash Vaezi
CC BY-SA 4.0
2021-09-16T13:59:50.930Z
About the geometric set cover. I am not sure if my estimated visibility polygons can be counted as objects in the geometric set cover. Although these visibility polygons has shared a lot of small regions and perhaps we can count on the frequency of the small regions in the related set cover instance, i am not sure if there is any paper that counts on the visibility polygons as objects.
Arash Vaezi
CC BY-SA 4.0
2021-09-16T14:03:10.277Z
Please inform me about the last results on geometric set cover.
Arash Vaezi
CC BY-SA 4.0
2021-09-16T20:21:41.797Z
See following papers and references. https://epubs.siam.org/doi/abs/10.1137/1.9781611973099.125, https://arxiv.org/abs/1403.0835, https://arxiv.org/pdf/2003.13420.pdf, http://chekuri.cs.illinois.edu/papers/fast-geometric-lp.pdf. These are only a few that came to mind but there are several others which are hopefully covered in the references.
Chandra Chekuri
CC BY-SA 4.0
2021-09-16T20:31:46.283Z
I also want to say that the art gallery problem may not be part of the progress - thought that it is worth pointing out the other cases since the wikepedia page is not updated.
Chandra Chekuri
<set-cover><polygon>
A Simpler Solution for a special case of the Set Cover problem
Arash Vaezi
# A Simpler Solution for a special case of the Set Cover problem

(Asked by: username_0 on 2021-09-16)

We decomposed a simple polygon into many small regions. Then we estimated a visibility polygon of a point by a subset of the small regions. Now I need the minimum set of visibility polygons that can cover all the small regions, the whole polygon. This can be seen as an instance of the Set Cover problem. However, I need an easier approach. As we deal with visibility polygons inside a simple polygon there must be an easier way than a general instance of the Set Cover problem.

**Tags:** set-cover, polygon
> **Comments:**
> **username_1**: for reference, the problem is NP-hard, but it looks like there is a polytime constant-factor approximation algorithm, and maybe a PTAS [https://en.wikipedia.org/wiki/Art_gallery_problem].  If for some reason you need to do it via set cover, properly formulated, it may be a special case of geometric set cover, which is somewhat easier than general set cover [https://en.wikipedia.org/wiki/Geometric_set_cover_problem].  
> **username_2**: The wikipedia page on geometric set cover is out of date. It does not refer to the large amount of progress made in the last decade or so.  
> **username_0**: Thank you. A PTAS algorithm for the general Art Gallery problem cannot be provided and constant approximation factor provided by Gosh in arXiv is not correct. As far as I know, a constant factor approximation algorithm for the Art Gallery problem is still open.  
> **username_0**: About the geometric set cover. I am not sure if my estimated visibility polygons can be counted as objects in the geometric set cover. Although these visibility polygons has shared a lot of small regions and perhaps we can count on the frequency of the small regions in the related set cover instance, i am not sure if there is any paper that counts on the visibility polygons as objects.  
> **username_0**: Please inform me about the last results on geometric set cover.  
> **username_2**: See following papers and references. https://epubs.siam.org/doi/abs/10.1137/1.9781611973099.125, https://arxiv.org/abs/1403.0835, https://arxiv.org/pdf/2003.13420.pdf, http://chekuri.cs.illinois.edu/papers/fast-geometric-lp.pdf. These are only a few that came to mind but there are several others which are hopefully covered in the references.  
> **username_2**: I also want to say that the art gallery problem may not be part of the progress - thought that it is worth pointing out the other cases since the wikepedia page is not updated.  

---

## 0 answers

