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.

  • 1
    $\begingroup$ for reference, the problem is NP-hard, but it looks like there is a polytime constant-factor approximation algorithm, and maybe a PTAS [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 [en.wikipedia.org/wiki/Geometric_set_cover_problem]. $\endgroup$
    – Neal Young
    Sep 16 at 13:13
  • $\begingroup$ 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. $\endgroup$ Sep 16 at 13:50
  • $\begingroup$ 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. $\endgroup$ Sep 16 at 13:54
  • $\begingroup$ 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. $\endgroup$ Sep 16 at 13:59
  • $\begingroup$ Please inform me about the last results on geometric set cover. $\endgroup$ Sep 16 at 14:03

Your Answer

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

Browse other questions tagged or ask your own question.