Document Open Access Logo

Half-Guarding Weakly-Visible Polygons and Terrains

Authors Nandhana Duraisamy, Hannah Miller Hillberg, Ramesh K. Jallu , Erik Krohn , Anil Maheshwari, Subhas C. Nandy, Alex Pahlow

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.18.pdf
  • Filesize: 1.28 MB
  • 17 pages

Document Identifiers

Author Details

Nandhana Duraisamy
  • PSG College of Technology, Coimbatore, India
Hannah Miller Hillberg
  • University of Wisconsin, Oshkosh, WI, USA
Ramesh K. Jallu
  • Indian Institute of Information Technology Raichur, India
Erik Krohn
  • University of Wisconsin, Oshkosh, WI, USA
Anil Maheshwari
  • Carleton University, Ottawa, Canada
Subhas C. Nandy
  • Indian Statistical Institute, Kolkata, India
Alex Pahlow
  • University of Wisconsin, Oshkosh, WI, USA

Cite As Get BibTex

Nandhana Duraisamy, Hannah Miller Hillberg, Ramesh K. Jallu, Erik Krohn, Anil Maheshwari, Subhas C. Nandy, and Alex Pahlow. Half-Guarding Weakly-Visible Polygons and Terrains. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.18

Abstract

We consider a variant of the art gallery problem where all guards are limited to seeing 180degree. Guards that can only see in one direction are called half-guards. We give a polynomial time approximation scheme for vertex guarding the vertices of a weakly-visible polygon with half-guards. We extend this to vertex guarding the boundary of a weakly-visible polygon with half-guards. We also show NP-hardness for vertex guarding a weakly-visible polygon with half-guards. Lastly, we show that the orientation of half-guards is critical in terrain guarding. Depending on the orientation of the half-guards, the problem is either very easy (polynomial time solvable) or very hard (NP-hard).

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Art Gallery Problem
  • Approximation Algorithm
  • NP-Hardness
  • Monotone Polygons
  • Half-Guards

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • This paper combines the results of [Nandhana Duraisamy et al., 2019] and [Hannah Miller Hillberg et al., 2022], which were obtained independently. The first gave a PTAS for vertex guarding the boundary of a weakly-visible polygon. The second gave a PTAS for vertex guarding the vertices of a weakly-visible polygon and provided hardness results for half-guarding terrains and weakly-visible polygons. A preliminary version of [Hannah Miller Hillberg et al., 2022] is presented in the Iranian Conference on Computational Geometry 2022 (an informal meeting).
  • Previous Version https://iccg2022.ce.sharif.edu/files/Papers/4-Guarding-Weakly-Visible-Polygons-with-Half-Guards.pdf

References

  1. Alok Aggarwal. The art gallery theorem: its variations, applications and algorithmic aspects. PhD thesis, The Johns Hopkins University, 1984. Google Scholar
  2. Stav Ashur, Omrit Filtser, and Matthew Katz. A constant-factor approximation algorithm for vertex guarding a WV-polygon. Journal of Computational Geometry, 12(1), December 2021. URL: https://doi.org/10.20382/jocg.v12i1a6.
  3. Stav Ashur, Omrit Filtser, Matthew J. Katz, and Rachel Saban. Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains. Computational Geometry, 101:101832, 2022. URL: https://doi.org/10.1016/j.comgeo.2021.101832.
  4. Pritam Bhattacharya, Subir Ghosh, and Bodhayan Roy. Approximability of guarding weak visibility polygons. Discrete Applied Mathematics, 228, February 2017. URL: https://doi.org/10.1016/j.dam.2016.12.015.
  5. Danny Z. Chen, Vladimir Estivill-Castro, and Jorge Urrutia. Optimal guarding of polygons and monotone chains. In Proceedings of the 7th Canadian Conference on Computational Geometry, Quebec City, Quebec, Canada, August 1995, pages 133-138. Carleton University, Ottawa, Canada, 1995. URL: http://www.cccg.ca/proceedings/1995/cccg1995_0022.pdf.
  6. Marcelo C. Couto, Pedro J. de Rezende, and Cid C. de Souza. An exact algorithm for minimizing vertex guards on art galleries. Int. Trans. Oper. Res., 18(4):425-448, 2011. URL: https://doi.org/10.1111/j.1475-3995.2011.00804.x.
  7. Nandhana Duraisamy, Ramesh K. Jallu, Anil Maheshwari, and Subhas C. Nandy. A PTAS for vertex guarding weakly-visible polygons using half-guards. Unpublished Manuscript, 2019. Google Scholar
  8. Stephan Eidenbenz. Inapproximability results for guarding polygons without holes. In ISAAC, pages 427-436, 1998. URL: https://doi.org/10.1007/3-540-49381-6_45.
  9. Khaled M. Elbassioni, Erik Krohn, Domagoj Matijevic, Julián Mestre, and Domagoj Severdija. Improved approximations for guarding 1.5-dimensional terrains. Algorithmica, 60(2):451-463, 2011. URL: https://doi.org/10.1007/s00453-009-9358-4.
  10. Stephan Friedrichs, Michael Hemmer, James King, and Christiane Schmidt. The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS. J. Comput. Geom., 7(1):256-284, 2016. URL: https://doi.org/10.20382/jocg.v7i1a13.
  11. Subir Kumar Ghosh. On recognizing and characterizing visibility graphs of simple polygons. Discrete & Computational Geometry, 17(2):143-162, 1997. URL: https://doi.org/10.1007/BF02770871.
  12. Hannah Miller Hillberg, Erik Krohn, and Alex Pahlow. Guarding weakly-visible polygons with half-guards. Iranian Conference on Computational Geometry, 2022. URL: https://iccg2022.ce.sharif.edu/files/Papers/4-Guarding-Weakly-Visible-Polygons-with-Half-Guards.pdf.
  13. James King and Erik Krohn. Terrain guarding is NP-hard. SIAM J. Comput., 40(5):1316-1339, 2011. URL: https://doi.org/10.1137/100791506.
  14. Erik Krohn. Survey of terrain guarding and art gallery problems. Comprehensive Exam, University of Iowa, November 2007. URL: http://faculty.cs.uwosh.edu/faculty/krohn/papers/comprehensive.pdf.
  15. Erik Krohn and Bengt J. Nilsson. Approximate guarding of monotone and rectilinear polygons. Algorithmica, 66(3):564-594, 2013. URL: https://doi.org/10.1007/s00453-012-9653-3.
  16. Alexander Kröller, Tobias Baumgartner, Sándor P. Fekete, and Christiane Schmidt. Exact solutions and bounds for general art gallery problems. ACM J. Exp. Algorithmics, 17, May 2012. URL: https://doi.org/10.1145/2133803.2184449.
  17. D. T. Lee and A. K. Lin. Computational complexity of art gallery problems. IEEE Trans. Inform. Theory, 32(2):276-282, March 1986. Google Scholar
  18. David Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11:329-343, 1982. Google Scholar
  19. Nabil H. Mustafa, Rajiv Raman, and Saurabh Ray. QPTAS for geometric set-cover problems via optimal separators. CoRR, abs/1403.0835, 2014. URL: http://arxiv.org/abs/1403.0835.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact