Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Parameterized Complexity of Guarding Almost Convex Polygons

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of Art Gallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow in 24th Annual European Symposium on Algorithms (Aarhus 2016)], the classic variant has an \({{\mathcal {O}}}(\log k)\)-approximation algorithm [Bonnet and Miltzow in 33rd International Symposium on Computational Geometry (Brisbane 2017)], and it may require irrational guards [Abrahamsen et al. in 33rd International Symposium on Computational Geometry (Brisbane 2017)]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be \(\exists {\mathbb {R}}\)-complete [Abrahamsen et al. in 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018)]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Workshop on Fixed-Parameter Computational Geometry (Leiden 2016)]: Is Art Gallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of Art Gallery, this case can also be viewed as the classic Dominating Set problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-Vertex Art Gallery is solvable in time \(r^{{{\mathcal {O}}}(r^2)}\hspace{0.55542pt}{\cdot }\hspace{1.66656pt}n^{{{\mathcal {O}}}(1)}\). Furthermore, our approach extends to assert that Vertex-Boundary Art Gallery and Boundary-Vertex Art Gallery are both FPT as well. To this end, we utilize structural properties of “almost convex polygons” to present a two-stage reduction from Vertex-Vertex Art Gallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

Notes

  1. The X-Y Art Gallery problem, for any \(\textsc {X},\textsc {Y}\in \{\textsc {Point},\textsc {Boundary},\textsc {Vertex}\}\), is often loosely termed the Art Gallery problem. For example, in the survey of open problems by Ghosh and Goswami [27], the term Art Gallery problem refers to the Vertex-Vertex Art Gallery problem.

  2. A non-decreasing function (or sequence) is one that never decreases but can sometimes not increase.

  3. If v does not see any vertex in [i, j], the claim holds vacuously.

  4. We remark that we do not know whether it is possible that the first vertices would form a non-increasing (or non-decreasing) sequence and the last vertices would not. Our weaker claim suffices for our purposes.

  5. If \(x\in {{\,\mathrm{\textsf{reflex}\hspace{0.36667pt}}\,}}(P)\), by \(S\cap x\) we mean \(S\cap \{x\}\).

  6. To comply with the formal definition of a Turing reduction, by Yes we mean a set with a single trivial Yes-instance of Structured Art Gallery. Note that if \(r > k\), then we also have that \(r\geqslant 1\).

  7. CSP is an abbreviation of Constraint Satisfaction Problem, and 2 is the maximum arity of a constraint.

  8. In case \(e\in {{\,\mathrm{\textsf{reflex}\hspace{0.36667pt}}\,}}(P)\), we mean that e itself does not see any vertex in C.

  9. For example, in Fig. 4, neither \({{\,\mathrm{\textsf{first}\hspace{0.99991pt}}\,}}(4,[8,19])\) nor \({{\,\mathrm{\textsf{first}\hspace{0.99991pt}}\,}}(6,[8,19])\) is \({{\,\mathrm{\mathsf nil}\,}}\), but \({{\,\mathrm{\textsf{first}\hspace{0.99991pt}}\,}}(5,[8,19])={{\,\mathrm{\mathsf nil}\,}}\).

  10. In the third and fourth cases, unlike the first and second cases, we first define f for integers \(i>h'\) rather than for integers \(i<\ell '\). The correctness of the reduction relies on this choice of design (we further elaborate on this in footnote 14 in the proof).

  11. If \(e\in {{\,\mathrm{\textsf{reflex}\hspace{0.36667pt}}\,}}(P)\), by \({\alpha (x)}\in e\) we mean \({\alpha (x)}=e\).

  12. Here, induction is not mandatory. Instead, we can rely on the constraints marked with a tilde. However, these constraints are required for a different purpose (rather than only to encompass the inductive hypothesis). To highlight this, we prefer to use induction.

  13. See “guarding the middle vertices in a convex region” in Sect. 3.3.

  14. If the function f were defined first for \(i<\ell '\) rather than for \(i>h'\), then the existence of \({\widehat{\delta }}\) would not have followed. Specifically, we need the integer that “propagates” in the definition of \({\widehat{f}}\) to be N rather than 0 because we have the assertion \(\alpha (x)\geqslant {\widehat{f}}(\alpha (x'))\) rather than \(\alpha (x)\leqslant {\widehat{f}}(\alpha (x'))\).

References

  1. Abrahamsen, M., Adamaszek, A., Miltzow, T.: Irrational guards are sometimes needed. In: 33rd International Symposium on Computational Geometry (Brisbane 2017). Leibniz Int. Proc. Inform., vol. 77, \(\#\,3\). Leibniz-Zent. Inform., Wadern (2017)

  2. Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is \(\exists {\mathbb{R}}\)-complete. In: 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018), pp. 65–73. ACM, New York (2018)

  3. Aggarwal, A.: The Art Gallery Theorem: Its Variations, Applications and Algorithmic Aspects. PhD thesis, Johns Hopkins University (1986)

  4. Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inform. Process. Lett. 8(3), 121–123 (1979)

    Article  MathSciNet  Google Scholar 

  5. Avis, D., Toussaint, G.T.: An efficient algorithm for decomposing a polygon into star-shaped polygons. Pattern Recognit. 13(6), 395–398 (1981)

    Article  ADS  MathSciNet  Google Scholar 

  6. Basu, S., Pollack, R., Roy, M.-F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43(6), 1002–1045 (1996)

    Article  MathSciNet  Google Scholar 

  7. Bhattacharya, P., Ghosh, S.K., Pal, S.P.: Constant approximation algorithms for guarding simple polygons using vertex guards (2017). arXiv:1712.05492

  8. Bhattacharya, P., Ghosh, S.K., Roy, B.: Approximability of guarding weak visibility polygons. Discrete Appl. Math. 228, 109–129 (2017)

    Article  MathSciNet  Google Scholar 

  9. Bonnet, É., Miltzow, T.: Parameterized hardness of art gallery problems. In: 24th Annual European Symposium on Algorithms (Aarhus 2016). Leibniz Int. Proc. Inform., vol. 57, # 19. Leibniz-Zent. Inform., Wadern (2016)

  10. Bonnet, É., Miltzow, T.: An approximation algorithm for the art gallery problem. In: 33rd International Symposium on Computational Geometry (Brisbane 2017). Leibniz Int. Proc. Inform., vol. 77, # 20. Leibniz-Zent. Inform., Wadern (2017)

  11. Bonnet, É., Miltzow, T.: Parameterized hardness of art gallery problems. ACM Trans. Algorithms 16(4), \(\#\,42\) (2020)

  12. Borrmann, D., de Rezende, P.J., de Souza, C.C., Fekete, S.P., Friedrichs, S., Kröller, A., Nüchter, A., Schmidt, C., Tozoni, D.C.: Point guards and point clouds: solving general art gallery problems. In: 29th Symposuim on Computational Geometry (Rio de Janeiro 2013), pp. 347–348. ACM, New York (2013)

  13. Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463–479 (1995)

    Article  MathSciNet  Google Scholar 

  14. Chvátal, V.A.: A combinatorial theorem in plane geometry. J. Comb. Theory Ser. B 18(1), 39–41 (1975)

    Article  MathSciNet  Google Scholar 

  15. Clarkson, K.L.: Algorithms for polytope covering and approximation. In: Algorithms and Data Structures (Montréal 1993). Lecture Notes in Computer Science, vol. 709, pp. 246–252. Springer, Berlin (1993)

  16. Couto, M.C., de Rezende, P.J., de Souza, C.C.: An exact algorithm for minimizing vertex guards on art galleries. Int. Trans. Oper. Res. 18(4), 425–448 (2011)

    Article  MathSciNet  Google Scholar 

  17. Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015)

  18. Deshpande, A., Kim, T., Demaine, E.D., Sarma, S.E.: A pseudopolynomial time \(O(\log n)\)-approximation algorithm for art gallery problems. In: Algorithms and Data Structures (Halifax 2007). Lecture Notes in Computer Science, vol. 4619, pp. 163–174. Springer, Berlin (2007)

  19. Diestel, R.: Graph Theory. Springer, Heidelberg (2012)

    Google Scholar 

  20. Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)

  21. Efrat, A., Har-Peled, S.: Guarding galleries and terrains. Inform. Process. Lett. 100(6), 238–245 (2006)

    Article  MathSciNet  Google Scholar 

  22. Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability of some art gallery problems. In: 10th Canadian Conference on Computational Geometry (Montréal 1998), \(\#\,23\). https://cccg.ca/proceedings/1998/

  23. Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31(1), 79–113 (2001)

    Article  MathSciNet  Google Scholar 

  24. Fisk, S.: A short proof of Chvátal’s watchman theorem. J. Comb. Theory Ser. B 24(3), 374 (1978)

    Article  Google Scholar 

  25. Ghosh, S.K.: Approximation algorithms for art gallery problems. In: Canadian Information Processing Society Congress (Winnipeg 1987), pp. 429–434. CIPS, Toronto (1987)

  26. Ghosh, S.K.: Approximation algorithms for art gallery problems in polygons. Discrete Appl. Math. 158(6), 718–722 (2010)

    Article  MathSciNet  Google Scholar 

  27. Ghosh, S.K., Goswami, P.P.: Unsolved problems in visibility graphs of points, segments, and polygons. ACM Comput. Surveys 46(2), \(\#\,22\) (2013)

  28. Giannopoulos, P.: Open problems: guarding problems. In: Lorentz Workshop on Fixed-Parameter Computational Geometry (Leiden 2016)

  29. Gilbers, A., Klein, R.: A new upper bound for the VC-dimension of visibility regions. Comput. Geom. 47(1), 61–74 (2014)

    Article  MathSciNet  Google Scholar 

  30. Golovach, P.A., Lokshtanov, D., Saurabh, S., Zehavi, M.: Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2018), pp. 262–273. SIAM, Philadelphia (2018)

  31. Hengeveld, S.B., Miltzow, T.: A practical algorithm with performance guarantees for the art gallery problem. In: 37th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 189, # 44. Leibniz-Zent. Inform., Wadern (2021)

  32. Kalai, G., Matoušek, J.: Guarding galleries where every point sees a large area. Isr. J. Math. 101, 125–139 (1997)

  33. Katz, M.J.: A PTAS for vertex guarding weakly-visible polygons—an extended abstract (2018). arXiv:1803.02160

  34. Katz, M.J., Roisman, G.S.: On guarding the vertices of rectilinear domains. Comput. Geom. 39(3), 219–228 (2008)

    Article  MathSciNet  Google Scholar 

  35. King, J.: Fast vertex guarding for polygons with and without holes. Comput. Geom. 46(3), 219–231 (2013)

    Article  MathSciNet  Google Scholar 

  36. King, J., Kirkpatrick, D.G.: Improved approximation for guarding simple galleries from the perimeter. Discrete Comput. Geom. 46(2), 252–269 (2011)

    Article  MathSciNet  Google Scholar 

  37. Kirkpatrick, D.: An \(O({\rm lg}\,{\rm lg}\,{ OPT})\)-approximation algorithm for multi-guarding galleries. Discrete Comput. Geom. 53(2), 327–343 (2015)

    Article  MathSciNet  Google Scholar 

  38. Kooshesh, A.A., Moret, B.M.E.: Three-coloring the vertices of a triangulated simple polygon. Pattern Recognit. 25(4), 443 (1992)

    Article  ADS  Google Scholar 

  39. Krohn, E.A., Nilsson, B.J.: Approximate guarding of monotone and rectilinear polygons. Algorithmica 66(3), 564–594 (2013)

    Article  MathSciNet  Google Scholar 

  40. Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inform. Theory 32(2), 276–282 (1986)

    Article  MathSciNet  Google Scholar 

  41. Niedermeier, R.: Ubiquitous parameterization—invitation to fixed-parameter algorithms. In: 29th International Symposium on Mathematical Foundations of Computer Science (Prague 2004). Lecture Notes in Computer Science, vol. 3153, pp. 84–103. Springer, Berlin (2004)

  42. Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: 27th International Symposium on Theoretical Aspects of Computer Science (Nancy 2010). Leibniz Int. Proc. Inform., vol. 5, pp. 17–32. Leibniz-Zent. Inform., Wadern (2010)

  43. O’Rourke, J.: Art Gallery Theorems and Algorithms. International Series of Monographs on Computer Science. Oxford University Press, Oxford (1987)

  44. O’Rourke, J., Supowit, K.J.: Some NP-hard polygon decomposition problems. IEEE Trans. Inform. Theory 29(2), 181–189 (1983)

    Article  MathSciNet  Google Scholar 

  45. de Rezende, P.J., de Souza, C.C., Friedrichs, S., Hemmer, M., Kröller, A., Tozoni, D.C.: Engineering art galleries. In: Algorithm Engineering. Lecture Notes in Computer Science, vol. 9220, pp. 379–417. Springer, Cham (2016)

  46. Schuchardt, D., Hecker, H.-D.: Two NP-hard art-gallery problems for ortho-polygons. Math. Logic Quart. 41(2), 261–267 (1995)

    Article  MathSciNet  Google Scholar 

  47. Shermer, T.C.: Recent results in art galleries. Proc. IEEE 80(9), 1384–1399 (1992)

    Article  Google Scholar 

  48. Urrutia, J.: Art gallery and illumination problems. In: Handbook of Computational Geometry, pp. 973–1027. North-Holland, Amsterdam (2000)

  49. Valtr, P.: Guarding galleries where no point sees a small area. Isr. J. Math 104(1), 1–16 (1998)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We thank anonymous reviewers for the SoCG 2020 version of this paper, for helpful comments that improved and simplified the paper.

Author information

Authors and Affiliations

  1. Indian Institute of Technology Madras, Chennai, India

    Akanksha Agrawal

  2. University of Bergen, Bergen, Norway

    Kristine V. K. Knudsen & Saket Saurabh

  3. University of California Santa Barbara, Santa Barbara, USA

    Daniel Lokshtanov

  4. Institute of Mathematical Sciences, Chennai, India

    Saket Saurabh

  5. Ben-Gurion University of the Negev, Beersheba, Israel

    Meirav Zehavi

Authors
  1. Akanksha Agrawal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kristine V. K. Knudsen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniel Lokshtanov
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Saket Saurabh
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Meirav Zehavi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Akanksha Agrawal.

Additional information

Editor in Charge: Kenneth Clarkson

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this article appeared at the 36th International Symposium on Computational Geometry (SoCG 2020).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Agrawal, A., Knudsen, K.V.K., Lokshtanov, D. et al. The Parameterized Complexity of Guarding Almost Convex Polygons. Discrete Comput Geom 71, 358–398 (2024). https://doi.org/10.1007/s00454-023-00569-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-023-00569-y

Keywords

Mathematics Subject Classification

Search

Navigation