{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:28Z","timestamp":1771036348032,"version":"3.50.1"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319539249","type":"print"},{"value":"9783319539256","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-53925-6_5","type":"book-chapter","created":{"date-parts":[[2017,2,19]],"date-time":"2017-02-19T20:12:36Z","timestamp":1487535156000},"page":"54-65","source":"Crossref","is-referenced-by-count":7,"title":["On Guarding Orthogonal Polygons with Sliding Cameras"],"prefix":"10.1007","author":[{"given":"Therese","family":"Biedl","sequence":"first","affiliation":[]},{"given":"Timothy M.","family":"Chan","sequence":"additional","affiliation":[]},{"given":"Stephanie","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Saeed","family":"Mehrabi","sequence":"additional","affiliation":[]},{"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[]},{"given":"Hamideh","family":"Vosoughpour","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,21]]},"reference":[{"key":"5_CR1","unstructured":"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)"},{"issue":"12","key":"5_CR2","doi-asserted-by":"crossref","first-page":"910","DOI":"10.1109\/TC.1981.1675729","volume":"30","author":"D Avis","year":"1981","unstructured":"Avis, D., Toussaint, G.T.: An optimal algorithm for determining the visibility of a polygon from an edge. IEEE Trans. Comput. 30(12), 910\u2013914 (1981)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"5_CR3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B Baker","year":"1994","unstructured":"Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-3-319-12691-3_10","volume-title":"Combinatorial Optimization and Applications","author":"M Berg de","year":"2014","unstructured":"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\u2013125. Springer, Heidelberg (2014). doi: 10.1007\/978-3-319-12691-3_10"},{"key":"5_CR5","unstructured":"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\u201317:13 (2016)"},{"issue":"4","key":"5_CR6","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discret. Comput. Geom. 14(4), 463\u2013479 (1995)","journal-title":"Discret. Comput. Geom."},{"key":"5_CR7","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: A combinatorial theorem in plane geometry. J. Comb. Theory Ser. B 18, 39\u201341 (1975)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"5_CR8","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"KL Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. Discret. Comput. Geom. 37(1), 43\u201358 (2007)","journal-title":"Discret. Comput. Geom."},{"issue":"1","key":"5_CR9","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"5_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Mark, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015)"},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-642-54423-1_26","volume-title":"LATIN 2014: Theoretical Informatics","author":"S Durocher","year":"2014","unstructured":"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\u2013305. Springer, Heidelberg (2014). doi: 10.1007\/978-3-642-54423-1_26"},{"key":"5_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/978-3-642-40313-2_29","volume-title":"Mathematical Foundations of Computer Science 2013","author":"S Durocher","year":"2013","unstructured":"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\u2013324. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40313-2_29"},{"issue":"1","key":"5_CR13","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s00453-001-0040-8","volume":"31","author":"S Eidenbenz","year":"2001","unstructured":"Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31(1), 79\u2013113 (2001)","journal-title":"Algorithmica"},{"key":"5_CR14","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem in NP-complete. SIAM J. Appl. Math. 32, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"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\u201348 (1991)","DOI":"10.1109\/SFCS.1991.185346"},{"issue":"2","key":"5_CR16","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1137\/0604020","volume":"4","author":"J Kahn","year":"1983","unstructured":"Kahn, J., Klawe, M.M., Kleitman, D.J.: Traditional galleries require fewer watchmen. SIAM J. Algebraic Discrete Methods 4(2), 194\u2013206 (1983)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"2","key":"5_CR17","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.comgeo.2004.07.002","volume":"30","author":"MJ Katz","year":"2005","unstructured":"Katz, M.J., Mitchell, J.S.B., Nir, Y.: Orthogonal segment stabbing. Comput. Geom. 30(2), 197\u2013205 (2005)","journal-title":"Comput. Geom."},{"issue":"2","key":"5_CR18","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1142\/S0218195911003639","volume":"21","author":"MJ Katz","year":"2011","unstructured":"Katz, M.J., Morgenstern, G.: Guarding orthogonal art galleries with sliding cameras. Int. J. Comput. Geom. Appl. 21(2), 241\u2013250 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"5_CR19","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.comgeo.2007.02.002","volume":"39","author":"MJ Katz","year":"2008","unstructured":"Katz, M.J., Roisman, G.S.: On guarding the vertices of rectilinear domains. Comput. Geom. 39(3), 219\u2013228 (2008)","journal-title":"Comput. Geom."},{"issue":"2","key":"5_CR20","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s00454-014-9656-8","volume":"53","author":"DG Kirkpatrick","year":"2015","unstructured":"Kirkpatrick, D.G.: An $$O(\\lg \\lg opt)$$ -approximation algorithm for multi-guarding galleries. Discrete Comput. Geom. 53(2), 327\u2013343 (2015)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"5_CR21","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1007\/s00453-012-9653-3","volume":"66","author":"E Krohn","year":"2013","unstructured":"Krohn, E., Nilsson, B.J.: Approximate guarding of monotone and rectilinear polygons. Algorithmica 66(3), 564\u2013594 (2013)","journal-title":"Algorithmica"},{"issue":"2","key":"5_CR22","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"DT Lee","year":"1986","unstructured":"Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32(2), 276\u2013282 (1986)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Lubiw, A.: Decomposing polygonal regions into convex quadrilaterals. In: Proceedings of the ACM Symposium on Computational Geometry (SoCG 1985), pp. 97\u2013106 (1985)","DOI":"10.1145\/323233.323247"},{"key":"5_CR24","unstructured":"Mehrabi, S.: Geometric optimization problems on orthogonal polygons: hardness results and approximation algorithms. Ph.D. thesis, University of Manitoba, Winnipeg, Canada, August 2015"},{"key":"5_CR25","unstructured":"O\u2019Rourke, J.: The complexity of computing minimum convex covers for polygons. In: 20th Allerton Conference Communication, Control, and Computing, pp. 75\u201384 (1982)"},{"key":"5_CR26","first-page":"273","volume":"14","author":"J O\u2019Rourke","year":"1983","unstructured":"O\u2019Rourke, J.: Galleries need fewer mobile guards: a variation to Chv\u00e1tal\u2019s theorem. Geom. Dedicata 14, 273\u2013283 (1983)","journal-title":"Geom. Dedicata"},{"key":"5_CR27","series-title":"The International Series of Monographs on Computer Science","volume-title":"Art Gallery Theorems and Algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. The International Series of Monographs on Computer Science. Oxford University Press, New York (1987)"},{"issue":"2","key":"5_CR28","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1002\/malq.19950410212","volume":"41","author":"D Schuchardt","year":"1995","unstructured":"Schuchardt, D., Hecker, H.: Two NP-hard art-gallery problems for ortho-polygons. Math. Logic Q. 41(2), 261\u2013267 (1995)","journal-title":"Math. Logic Q."},{"key":"5_CR29","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R Tamassia","year":"1986","unstructured":"Tamassia, R., Tollis, I.: A unified approach a visibility representation of planar graphs. Discrete Comput. Geom. 1, 321\u2013341 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"5_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-642-40164-0_29","volume-title":"Fundamentals of Computation Theory","author":"AP Tom\u00e1s","year":"2013","unstructured":"Tom\u00e1s, A.P.: Guarding thin orthogonal polygons is hard. In: G\u0105sieniec, L., Wolter, F. (eds.) FCT 2013. LNCS, vol. 8070, pp. 305\u2013316. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40164-0_29"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53925-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T06:54:18Z","timestamp":1498373658000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53925-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319539249","9783319539256"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53925-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}