{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:35:56Z","timestamp":1743057356489,"version":"3.40.3"},"publisher-location":"Cham","reference-count":69,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030500252"},{"type":"electronic","value":"9783030500269"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-50026-9_2","type":"book-chapter","created":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T23:02:43Z","timestamp":1592780563000},"page":"16-29","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Parameterized Analysis of Art Gallery and Terrain Guarding"],"prefix":"10.1007","author":[{"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"issue":"3","key":"2_CR1","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF02570710","volume":"14","author":"J Abello","year":"1995","unstructured":"Abello, J., Egecioglu, O., Kumar, K.: Visibility graphs of staircase polygons and the weak bruhat order I: from visibility graphs to maximal chains. Discrete Comput. Geom. 14(3), 331\u2013358 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"2_CR2","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: Irrational guards are sometimes needed. In: 33rd International Symposium on Computational Geometry (SoCG), pp. 3:1\u20133:15 (2017)"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R}$$-complete. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 65\u201373 (2018)","DOI":"10.1145\/3188745.3188868"},{"key":"2_CR4","unstructured":"Aggarwal, A.: The art gallery theorem: its variations, applications and algorithmic aspects. Ph.D. thesis, The Johns Hopkins University, Baltimore, Maryland (1986)"},{"key":"2_CR5","unstructured":"Agrawal, A., Knudsen, K., Daniel Lokshtanov, S.S., Zehavi, M.: The parameterized complexity of guarding almost convex polygons. In: 36rd International Symposium on Computational Geometry (SoCG) (2020, to appear)"},{"key":"2_CR6","unstructured":"Agrawal, A., Kolay, S., Zehavi, M.: Multivariate analysis for guarding terrains. In: Manuscript. p. TBA (2020)"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Ashok, P., Fomin, F.V., Kolay, S., Saurabh, S., Zehavi, M.: Exact algorithms for terrain guarding. ACM Trans. Algorithms 14(2), 25:1\u201325:20 (2018)","DOI":"10.1145\/3186897"},{"issue":"6","key":"2_CR8","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0031-3203(81)90002-9","volume":"13","author":"D Avis","year":"1981","unstructured":"Avis, D., Toussaint, G.T.: An efficient algorithm for decomposing a polygon into star-shaped polygons. Pattern Recogn. 13(6), 395\u2013398 (1981)","journal-title":"Pattern Recogn."},{"issue":"6","key":"2_CR9","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S Basu","year":"1996","unstructured":"Basu, S., Pollack, R., Roy, M.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43(6), 1002\u20131045 (1996)","journal-title":"J. ACM"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B.: A constant-factor approximation algorithm for optimal 1.5d terrain guarding. SICOMP 36(6), 1631\u20131647 (2007)","DOI":"10.1137\/S0097539704446384"},{"key":"2_CR11","unstructured":"Bhattacharya, P., Ghosh, S.K., Pal, S.P.: Constant approximation algorithms for guarding simple polygons using vertex guards. CoRR\/arXiv abs\/1712.05492 (2017)"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.dam.2016.12.015","volume":"228","author":"P Bhattacharya","year":"2017","unstructured":"Bhattacharya, P., Ghosh, S.K., Roy, B.: Approximability of guarding weak visibility polygons. Discrete Appl. Math. 228, 109\u2013129 (2017)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"2_CR13","first-page":"21","volume":"10","author":"\u00c9 Bonnet","year":"2019","unstructured":"Bonnet, \u00c9., Giannopoulos, P.: Orthogonal terrain guarding is NP-complete. J. Comput. Geom. 10(2), 21\u201344 (2019)","journal-title":"J. Comput. Geom."},{"key":"2_CR14","unstructured":"Bonnet, \u00c9., Miltzow, T.: Parameterized hardness of art gallery problems. In: Proceedings of the 24th Annual European Symposium on Algorithms (ESA), pp. 19:1\u201319:17 (2016)"},{"key":"2_CR15","unstructured":"Bonnet, \u00c9., Miltzow, T.: An approximation algorithm for the art gallery problem. In: Proceedings of the 33rd International Symposium on Computational Geometry (SoCG), pp. 20:1\u201320:15 (2017)"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Borrmann, D., et al.: Point guards and point clouds: solving general art gallery problems. In: Symposium on Computational Geometry (SoCG), pp. 347\u2013348 (2013)","DOI":"10.1145\/2462356.2462361"},{"issue":"4","key":"2_CR17","doi-asserted-by":"publisher","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. Discrete Comput. Geom. 14(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"2_CR18","unstructured":"Chen, D.Z., Estivill-Castro, V., Urrutia, J.: Optimal guarding of polygons and monotone chains. In: CCCG, pp. 133\u2013138 (1995)"},{"issue":"1","key":"2_CR19","doi-asserted-by":"publisher","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(1), 39\u2013741 (1975)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"2_CR20","doi-asserted-by":"publisher","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. Discrete Comput. Geom. 37(1), 43\u201358 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"2_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/3-540-57155-8_252","volume-title":"Algorithms and Data Structures","author":"KL Clarkson","year":"1993","unstructured":"Clarkson, K.L.: Algorithms for polytope covering and approximation. In: Dehne, F., Sack, J.-R., Santoro, N., Whitesides, S. (eds.) WADS 1993. LNCS, vol. 709, pp. 246\u2013252. Springer, Heidelberg (1993). \n                  https:\/\/doi.org\/10.1007\/3-540-57155-8_252"},{"issue":"4","key":"2_CR22","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1111\/j.1475-3995.2011.00804.x","volume":"18","author":"MC Couto","year":"2011","unstructured":"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\u2013448 (2011)","journal-title":"Int. Trans. Oper. Res."},{"key":"2_CR23","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Heidelberg (2015). \n                  https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"2_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-540-73951-7_15","volume-title":"Algorithms and Data Structures","author":"A Deshpande","year":"2007","unstructured":"Deshpande, A., Kim, T., Demaine, E.D., Sarma, S.E.: A pseudopolynomial time O(logn)-approximation algorithm for art gallery problems. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 163\u2013174. Springer, Heidelberg (2007). \n                  https:\/\/doi.org\/10.1007\/978-3-540-73951-7_15"},{"key":"2_CR25","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999). \n                  https:\/\/doi.org\/10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"2_CR26","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Heidelberg (2013). \n                  https:\/\/doi.org\/10.1007\/978-1-4471-5559-1","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"2_CR27","unstructured":"Durocher, S., Li, P.C., Mehrabi, S.: Guarding orthogonal terrains. In: Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG (2015)"},{"issue":"6","key":"2_CR28","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.ipl.2006.05.014","volume":"100","author":"A Efrat","year":"2006","unstructured":"Efrat, A., Har-Peled, S.: Guarding galleries and terrains. Inf. Process. Lett. 100(6), 238\u2013245 (2006)","journal-title":"Inf. Process. Lett."},{"key":"2_CR29","unstructured":"Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability of some art gallery problems. In: Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG) (1998)"},{"issue":"1","key":"2_CR30","doi-asserted-by":"publisher","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":"2_CR31","doi-asserted-by":"crossref","unstructured":"Elbassioni, M.K., Krohn, E., Matijevic, D., Mestre, J., Severdija, D.: Improved approximations for guarding 1.5-dimensional terrains. Algorithmica 60(2), 451\u2013463 (2011)","DOI":"10.1007\/s00453-009-9358-4"},{"issue":"1","key":"2_CR32","first-page":"108","volume":"6","author":"W Evans","year":"2015","unstructured":"Evans, W., Saeedi, N.: On characterizing terrain visibility graphs. J. Comput. Geom. 6(1), 108\u2013141 (2015)","journal-title":"J. Comput. Geom."},{"key":"2_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/11847250_25","volume-title":"Parameterized and Exact Computation","author":"MR Fellows","year":"2006","unstructured":"Fellows, M.R.: The lost continent of polynomial time: preprocessing and kernelization. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 276\u2013277. Springer, Heidelberg (2006). \n                  https:\/\/doi.org\/10.1007\/11847250_25"},{"issue":"3","key":"2_CR34","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/0095-8956(78)90059-X","volume":"24","author":"S Fisk","year":"1978","unstructured":"Fisk, S.: A short proof of Chv\u00e1tal\u2019s watchman theorem. J. Comb. Theory Ser. B 24(3), 374 (1978)","journal-title":"J. Comb. Theory Ser. B"},{"key":"2_CR35","doi-asserted-by":"publisher","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg (2006). \n                  https:\/\/doi.org\/10.1007\/3-540-29953-X","DOI":"10.1007\/3-540-29953-X"},{"key":"2_CR36","doi-asserted-by":"crossref","unstructured":"Fomin, F., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2018)","DOI":"10.1017\/9781107415157"},{"key":"2_CR37","unstructured":"Friedrichs, S., Hemmer, M., King, J., Schmidt, C.: The continuous 1.5D terrain guarding problem: discretization, optimal solutions, and PTAS. J. Comput. Geom. 7(1), 256\u2013284 (2016)"},{"key":"2_CR38","unstructured":"Ghosh, S.K.: Approximation algorithms for art gallery problems. In: Canadian Information Processing Society Congress, pp. 429\u2013434 (1987)"},{"key":"2_CR39","doi-asserted-by":"crossref","unstructured":"Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge University Press, Cambridge (2007)","DOI":"10.1017\/CBO9780511543340"},{"issue":"6","key":"2_CR40","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.dam.2009.12.004","volume":"158","author":"SK Ghosh","year":"2010","unstructured":"Ghosh, S.K.: Approximation algorithms for art gallery problems in polygons. Discrete Appl. Math. 158(6), 718\u2013722 (2010)","journal-title":"Discrete Appl. Math."},{"key":"2_CR41","doi-asserted-by":"crossref","unstructured":"Ghosh, S.K., Goswami, P.P.: Unsolved problems in visibility graphs of points, segments, and polygons. ACM Comput. Surv. 46(2), 22:1\u201322:29 (2013)","DOI":"10.1145\/2543581.2543589"},{"key":"2_CR42","unstructured":"Giannopoulos, P.: Open problems: guarding problems. In: Lorentz Workshop on Fixed-Parameter Computational Geometry, Leiden, the Netherlands, p. 12 (2016)"},{"issue":"1","key":"2_CR43","first-page":"168","volume":"5","author":"M Gibson","year":"2014","unstructured":"Gibson, M., Kanade, G., Krohn, E., Varadarajan, K.: Guarding terrains via local search. J. Comput. Geom. 5(1), 168\u2013178 (2014)","journal-title":"J. Comput. Geom."},{"issue":"1","key":"2_CR44","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.comgeo.2013.08.012","volume":"47","author":"A Gilbers","year":"2014","unstructured":"Gilbers, A., Klein, R.: A new upper bound for the VC-dimension of visibility regions. Comput. Geom. 47(1), 61\u201374 (2014)","journal-title":"Comput. Geom."},{"issue":"1","key":"2_CR45","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF02760925","volume":"101","author":"G Kalai","year":"1997","unstructured":"Kalai, G., Matou\u0161ek, J.: Guarding galleries where every point sees a large area. Israel J. Math. 101(1), 125\u2013139 (1997)","journal-title":"Israel J. Math."},{"key":"2_CR46","unstructured":"Katz, M.J.: A PTAS for vertex guarding weakly-visible polygons - an extended abstract. CoRR abs\/1803.02160 (2018)"},{"issue":"3","key":"2_CR47","doi-asserted-by":"publisher","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."},{"key":"2_CR48","unstructured":"Khodakarami, F., Didehvar, F., Mohades, A.: A fixed-parameter algorithm for guarding 1.5D terrains. Theor. Comput. Sci. 595, 130\u2013142 (2015)"},{"key":"2_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/11682462_58","volume-title":"LATIN 2006: Theoretical Informatics","author":"J King","year":"2006","unstructured":"King, J.: A 4-approximation algorithm for guarding 1.5-dimensional terrains. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 629\u2013640. Springer, Heidelberg (2006). \n                  https:\/\/doi.org\/10.1007\/11682462_58"},{"issue":"5","key":"2_CR50","doi-asserted-by":"publisher","first-page":"1316","DOI":"10.1137\/100791506","volume":"40","author":"J King","year":"2011","unstructured":"King, J., Krohn, E.: Terrain guarding is NP-hard. SICOMP 40(5), 1316\u20131339 (2011)","journal-title":"SICOMP"},{"issue":"3","key":"2_CR51","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.comgeo.2012.07.004","volume":"46","author":"J King","year":"2013","unstructured":"King, J.: Fast vertex guarding for polygons with and without holes. Comput. Geom. 46(3), 219\u2013231 (2013)","journal-title":"Comput. Geom."},{"issue":"2","key":"2_CR52","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/s00454-011-9352-x","volume":"46","author":"J King","year":"2011","unstructured":"King, J., Kirkpatrick, D.G.: Improved approximation for guarding simple galleries from the perimeter. Discrete Comput. Geom. 46(2), 252\u2013269 (2011)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"2_CR53","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00454-014-9656-8","volume":"53","author":"DG Kirkpatrick","year":"2015","unstructured":"Kirkpatrick, D.G.: An $$O(\\log \\log \\text{ OPT })$$-approximation algorithm for multi-guarding galleries. Discrete Comput. Geom. 53(2), 327\u2013343 (2015)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"2_CR54","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0031-3203(92)90093-X","volume":"25","author":"AA Kooshesh","year":"1992","unstructured":"Kooshesh, A.A., Moret, B.M.E.: Three-coloring the vertices of a triangulated simple polygon. Pattern Recogn. 25(4), 443 (1992)","journal-title":"Pattern Recogn."},{"issue":"3","key":"2_CR55","doi-asserted-by":"publisher","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":"2_CR56","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"D Lee","year":"1986","unstructured":"Lee, D., Lin, A.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32(2), 276\u2013282 (1986)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2_CR57","unstructured":"Lyu, Y., \u00dcng\u00f6r, A.: A fast 2-approximation algorithm for guarding orthogonal terrains. In: Proceedings of the 28th Canadian Conference on Computational Geometry, CCCG. pp. 161\u2013167 (2016)"},{"key":"2_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-3-642-30891-8_20","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"D Marx","year":"2012","unstructured":"Marx, D.: What\u2019s next? Future directions in parameterized complexity. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 469\u2013496. Springer, Heidelberg (2012). \n                  https:\/\/doi.org\/10.1007\/978-3-642-30891-8_20"},{"key":"2_CR59","unstructured":"Mehrabi, S.: Guarding the vertices of an orthogonal terrain using vertex guards. \n                  arXiv:1512.08292\n                  \n                 (2015)"},{"key":"2_CR60","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics and its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)"},{"key":"2_CR61","unstructured":"Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 17\u201332 (2010)"},{"key":"2_CR62","volume-title":"Art Gallery Theorems and Algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms, vol. 57. Oxford University Press, Oxford (1987)"},{"issue":"2","key":"2_CR63","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1109\/TIT.1983.1056648","volume":"29","author":"J O\u2019Rourke","year":"1983","unstructured":"O\u2019Rourke, J., Supowit, K.J.: Some NP-hard polygon decomposition problems. IEEE Trans. Inf. Theory 29(2), 181\u2013189 (1983)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2_CR64","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-319-49487-6_12","volume-title":"Algorithm Engineering","author":"PJ de Rezende","year":"2016","unstructured":"de Rezende, P.J., de Souza, C.C., Friedrichs, S., Hemmer, M., Kr\u00f6ller, A., Tozoni, D.C.: Engineering art galleries. In: Kliemann, L., Sanders, P. (eds.) Algorithm Engineering. LNCS, vol. 9220, pp. 379\u2013417. Springer, Cham (2016). \n                  https:\/\/doi.org\/10.1007\/978-3-319-49487-6_12"},{"key":"2_CR65","doi-asserted-by":"crossref","unstructured":"van Rooij, I., Blokpoel, M., Kwisthout, J., Wareham, T.: Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis. Cambridge University Press, Cambridge (2019)","DOI":"10.1017\/9781107358331"},{"issue":"2","key":"2_CR66","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1002\/malq.19950410212","volume":"41","author":"D Schuchardt","year":"1995","unstructured":"Schuchardt, D., Hecker, H.D.: Two NP-hard art-gallery problems for ortho-polygons. Math. Logic Q. 41(2), 261\u2013267 (1995)","journal-title":"Math. Logic Q."},{"issue":"9","key":"2_CR67","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1109\/5.163407","volume":"80","author":"TC Shermer","year":"1992","unstructured":"Shermer, T.C.: Recent results in art galleries (geometry). Proc. IEEE 80(9), 1384\u20131399 (1992)","journal-title":"Proc. IEEE"},{"issue":"1","key":"2_CR68","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1016\/B978-044482537-7\/50023-1","volume":"1","author":"J Urrutia","year":"2000","unstructured":"Urrutia, J.: Art gallery and illumination problems. Handb. Comput. Geom. 1(1), 973\u20131027 (2000)","journal-title":"Handb. Comput. Geom."},{"issue":"1","key":"2_CR69","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02897056","volume":"104","author":"P Valtr","year":"1998","unstructured":"Valtr, P.: Guarding galleries where no point sees a small area. Israel J. Math. 104(1), 1\u201316 (1998)","journal-title":"Israel J. Math."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-50026-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,11]],"date-time":"2020-10-11T07:14:02Z","timestamp":1602400442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-50026-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030500252","9783030500269"],"references-count":69,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-50026-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"22 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Yekaterinburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/csr2020.sciencesconf.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":">= 3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was cancelled as a live conference due to the corona pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}