Abstract
A sliding camera inside an orthogonal polygon P is a point guard that travels back and forth along an orthogonal line segment \(\gamma \) in P. The sliding camera g can see a point p in P if the perpendicular from p onto \(\gamma \) is inside P. In this paper, we give the first constant-factor approximation algorithm for the problem of guarding P with the minimum number of sliding cameras. Next, we show that the sliding guards problem is linear-time solvable if the (suitably defined) dual graph of the polygon has bounded treewidth. On the other hand, we show that the problem is NP-hard on orthogonal polygons with holes even if only horizontal cameras are allowed. Finally, we study art gallery theorems for sliding cameras, thus, give upper and lower bounds in terms of the number of sliding cameras needed relative to the number of vertices n.
T. Biedl and T.M. Chan—Research of the authors is supported by NSERC.
F. Montecchiani—Research of the author supported in part by the MIUR project AMANDA, prot. 2012C4E3KT_001. Research was done while the author was visiting the University of Waterloo.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aggarwal, A.: The art gallery theorem: its variations, applications and algorithmic aspects. Ph.D. thesis, Johns Hopkins University, A summary can be found in [27], Chap. 3 (1984)
Avis, D., Toussaint, G.T.: An optimal algorithm for determining the visibility of a polygon from an edge. IEEE Trans. Comput. 30(12), 910–914 (1981)
Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994)
de Berg, M., Durocher, S., Mehrabi, S.: Guarding monotone art galleries with sliding cameras in linear time. In: Zhang, Z., Wu, L., Xu, W., Du, D.-Z. (eds.) COCOA 2014. LNCS, vol. 8881, pp. 113–125. Springer, Heidelberg (2014). doi:10.1007/978-3-319-12691-3_10
Biedl, T., Mehrabi, S.: On r-guarding thin orthogonal polygons. In: 27th International Symposium on Algorithms and Computation (ISAAC 2016), LIPIcs, vol. 64, pp. 17:1–17:13 (2016)
Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discret. Comput. Geom. 14(4), 463–479 (1995)
Chvátal, V.: A combinatorial theorem in plane geometry. J. Comb. Theory Ser. B 18, 39–41 (1975)
Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. Discret. Comput. Geom. 37(1), 43–58 (2007)
Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Mark, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015)
Durocher, S., Filtser, O., Fraser, R., Mehrabi, A.D., Mehrabi, S.: A (7/2)-approximation algorithm for guarding orthogonal art galleries with sliding cameras. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 294–305. Springer, Heidelberg (2014). doi:10.1007/978-3-642-54423-1_26
Durocher, S., Mehrabi, S.: Guarding orthogonal art galleries using sliding cameras: algorithmic and hardness results. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 314–324. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40313-2_29
Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31(1), 79–113 (2001)
Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem in NP-complete. SIAM J. Appl. Math. 32, 826–834 (1977)
Hoffmann, F., Kaufmann, M., Kriegel, K.: The art gallery theorem for polygons with holes. In: Proceedings of Foundations of Computer Science (FOCS 1991), pp. 39–48 (1991)
Kahn, J., Klawe, M.M., Kleitman, D.J.: Traditional galleries require fewer watchmen. SIAM J. Algebraic Discrete Methods 4(2), 194–206 (1983)
Katz, M.J., Mitchell, J.S.B., Nir, Y.: Orthogonal segment stabbing. Comput. Geom. 30(2), 197–205 (2005)
Katz, M.J., Morgenstern, G.: Guarding orthogonal art galleries with sliding cameras. Int. J. Comput. Geom. Appl. 21(2), 241–250 (2011)
Katz, M.J., Roisman, G.S.: On guarding the vertices of rectilinear domains. Comput. Geom. 39(3), 219–228 (2008)
Kirkpatrick, D.G.: An \(O(\lg \lg opt)\)-approximation algorithm for multi-guarding galleries. Discrete Comput. Geom. 53(2), 327–343 (2015)
Krohn, E., Nilsson, B.J.: Approximate guarding of monotone and rectilinear polygons. Algorithmica 66(3), 564–594 (2013)
Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32(2), 276–282 (1986)
Lubiw, A.: Decomposing polygonal regions into convex quadrilaterals. In: Proceedings of the ACM Symposium on Computational Geometry (SoCG 1985), pp. 97–106 (1985)
Mehrabi, S.: Geometric optimization problems on orthogonal polygons: hardness results and approximation algorithms. Ph.D. thesis, University of Manitoba, Winnipeg, Canada, August 2015
O’Rourke, J.: The complexity of computing minimum convex covers for polygons. In: 20th Allerton Conference Communication, Control, and Computing, pp. 75–84 (1982)
O’Rourke, J.: Galleries need fewer mobile guards: a variation to Chvátal’s theorem. Geom. Dedicata 14, 273–283 (1983)
O’Rourke, J.: Art Gallery Theorems and Algorithms. The International Series of Monographs on Computer Science. Oxford University Press, New York (1987)
Schuchardt, D., Hecker, H.: Two NP-hard art-gallery problems for ortho-polygons. Math. Logic Q. 41(2), 261–267 (1995)
Tamassia, R., Tollis, I.: A unified approach a visibility representation of planar graphs. Discrete Comput. Geom. 1, 321–341 (1986)
Tomás, A.P.: Guarding thin orthogonal polygons is hard. In: Gąsieniec, L., Wolter, F. (eds.) FCT 2013. LNCS, vol. 8070, pp. 305–316. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40164-0_29
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Biedl, T., Chan, T.M., Lee, S., Mehrabi, S., Montecchiani, F., Vosoughpour, H. (2017). On Guarding Orthogonal Polygons with Sliding Cameras. In: Poon, SH., Rahman, M., Yen, HC. (eds) WALCOM: Algorithms and Computation. WALCOM 2017. Lecture Notes in Computer Science(), vol 10167. Springer, Cham. https://doi.org/10.1007/978-3-319-53925-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-53925-6_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53924-9
Online ISBN: 978-3-319-53925-6
eBook Packages: Computer ScienceComputer Science (R0)