Document Open Access Logo

On r-Guarding Thin Orthogonal Polygons

Authors Therese Biedl, Saeed Mehrabi

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.17.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Therese Biedl
Saeed Mehrabi

Cite As Get BibTex

Therese Biedl and Saeed Mehrabi. On r-Guarding Thin Orthogonal Polygons. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.17

Abstract

Guarding a polygon with few guards is an old and well-studied problem in computational geometry. Here we consider the following variant: We assume that the polygon is orthogonal and thin in some sense, and we consider a point p to guard a point q if and only if the minimum axis-aligned rectangle spanned by p and q is inside the polygon.

A simple proof shows that this problem is NP-hard on orthogonal polygons with holes, even if the polygon is thin. If there are no holes, then a thin polygon becomes a tree polygon in the sense that the so-called dual graph of the polygon is a tree. It was known that finding the minimum set of r-guards is polynomial for tree polygons (and in fact for all orthogonal polygons), but the run-time was ~O(n^17). We show here that with a different approach one can find the minimum set of r-guards can be found in tree polygons in linear time, answering a question posed by Biedl et al. (SoCG 2011). Furthermore, the approach is much more general, allowing to specify subsets of points to guard and guards to use, and it generalizes to polygons with h holes or thickness K, becoming fixed-parameter tractable in h + K.

Subject Classification

Keywords
  • Art Gallery Problem
  • Orthogonal Polygons
  • r-Guarding
  • Treewidth
  • Fixed-parameter Tractable

Metrics

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

References

  1. T. Biedl, M. T. Irfan, J. Iwerks, J. Kim, and J. S. B. Mitchell. Guarding polyominoes. In Proc. of the ACM Symp. on Computational Geometry (SoCG'11), pages 387-396, 2011. Google Scholar
  2. T. C. Biedl and S. Mehrabi. On r-guarding thin orthogonal polygons. CoRR, abs/1604.07100, 2016. URL: http://arxiv.org/abs/1604.07100.
  3. B. Chazelle. Triangulating a simple polygon in linear time. Disc. Comp. Geom., 6(5):485-524, 1991. Google Scholar
  4. V. Chvátal. A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Series B, 18:39-41, 1975. URL: http://dx.doi.org/10.1137/S0097539796302531.
  5. B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. Google Scholar
  6. J. Culberson and R. A. Reckhow. Orthogonally convex coverings of orthogonal polygons without holes. Journal of Computer and System Sciences, 39(2):166-204, 1989. Google Scholar
  7. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Mark, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, Heidelberg, Germany, 2015. Google Scholar
  8. S. Durocher and S. Mehrabi. Guarding orthogonal art galleries using sliding cameras: algorithmic and hardness results. In Proceedings of Mathematical Foundations of Computer Science (MFCS 2013), volume 8087 of LNCS, pages 314-324, 2013. Google Scholar
  9. S. Eidenbenz, C. Stamm, and P. Widmayer. Inapproximability results for guarding polygons and terrains. Algorithmica, 31(1):79-113, 2001. URL: http://dx.doi.org/10.1007/s00453-001-0040-8.
  10. D. S. Franzblau and D. J. Kleitman. An algorithm for constructing regions with rectangles: Independence and minimum generating sets for collections of intervals. In Proceedings of the ACM Symposium on Theory of Computing (STOC 1984), pages 167-174, 1984. Google Scholar
  11. M. R. Garey and D. S. Johnson. The Rectilinear Steiner Tree Problem is NP-complete. SIAM Journal of Applied Mathematics, 32:826-834, 1977. Google Scholar
  12. S. K. Ghosh. Approximation algorithms for art gallery problems in polygons. Disc. App. Math., 158(6):718-722, 2010. Google Scholar
  13. F. Kammer and T. Tholey. Approximate tree decompositions of planar graphs in linear time. In Proc. of the ACM-SIAM Symp. on Discrete Algorithms (SODA 2012), pages 683-698, 2012. Google Scholar
  14. G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996. Google Scholar
  15. M. J. Katz and G. Morgenstern. Guarding orthogonal art galleries with sliding cameras. Int. J. Comput. Geometry Appl., 21(2):241-250, 2011. Google Scholar
  16. J. M. Keil. Minimally covering a horizontally convex orthogonal polygon. In Proceedings of the ACM Symposium on Computational Geometry (SoCG 1986), pages 43-51, 1986. Google Scholar
  17. E. Krohn and B. J. Nilsson. Approximate guarding of monotone and rectilinear polygons. Algorithmica, 66(3):564-594, 2013. Google Scholar
  18. D. T. Lee and Arthur K. Lin. Computational complexity of art gallery problems. IEEE Trans. on Information Theory, 32(2):276-282, 1986. URL: http://dx.doi.org/10.1109/TIT.1986.1057165.
  19. A. Lingas, A. Wasylewicz, and P. Zylinski. Linear-time 3-approximation algorithm for the r-star covering problem. Int. J. Comput. Geometry Appl., 22(2):103-142, 2012. Google Scholar
  20. R. Motwani, A. Raghunathan, and H. Saran. Perfect graphs and orthogonally convex covers. SIAM J. Discrete Math., 2(3):371-392, 1989. Google Scholar
  21. J. O'Rourke. Art Gallery Theorems and Algorithms. The International Series of Monographs on Computer Science. Oxford University Press, New York, NY, 1987. Google Scholar
  22. L. Palios and P. Tzimas. Minimum r-star cover of class-3 orthogonal polygons. In Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA 2014), volume 8986 of LNCS, pages 286-297. Springer, 2015. Google Scholar
  23. S. Poljak. A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae, 15(2):307-309, 1974. Google Scholar
  24. D. Schuchardt and H.-D. Hecker. Two NP-hard art-gallery problems for ortho-polygons. Mathematical Logic Quarterly, 41(2):261-267, 1995. Google Scholar
  25. P. J. Slater. R-domination in graphs. J. ACM, 23(3):446-450, 1976. Google Scholar
  26. A. P. Tomás. Guarding thin orthogonal polygons is hard. In Proceedings of Fundamentals of Computation Theory (FCT 2013), volume 8070 of LNCS, pages 305-316, 2013. Google Scholar
  27. C. Worman and J. M. Keil. Polygon decomposition and the orthogonal art gallery problem. Int. J. Comput. Geometry Appl., 17(2):105-138, 2007. URL: http://dx.doi.org/10.1142/S0218195907002264.
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