{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T04:52:22Z","timestamp":1748321542292},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401633"},{"type":"electronic","value":"9783642401640"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40164-0_29","type":"book-chapter","created":{"date-parts":[[2013,7,22]],"date-time":"2013-07-22T01:01:30Z","timestamp":1374454890000},"page":"305-316","source":"Crossref","is-referenced-by-count":11,"title":["Guarding Thin Orthogonal Polygons Is Hard"],"prefix":"10.1007","author":[{"given":"Ana Paula","family":"Tom\u00e1s","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/j.ipl.2009.03.014","volume":"109","author":"M. Abellanas","year":"2009","unstructured":"Abellanas, M., Canales, S., Hern\u00e1ndez-Pe\u00f1alver, G.: An Art Gallery Theorem for Pyramids. Inf. Process. Lett.\u00a0109, 719\u2013721 (2009)","journal-title":"Inf. Process. Lett."},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness Results for Cubic Graphs. Theoretical Computer Science\u00a0237, 123\u2013134 (2000)","journal-title":"Theoretical Computer Science"},{"key":"29_CR3","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.tcs.2005.11.029","volume":"354","author":"M. Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science\u00a0354, 320\u2013338 (2006)","journal-title":"Theoretical Computer Science"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"Biedl, T., Irfan, M.T., Iwerks, J., Kim, J., Mitchell, J.S.B.: Guarding Polyominoes. In: 27th ACM Symp.\u00a0on Computational Geometry, pp. 387\u2013396. ACM (2011)","DOI":"10.1145\/1998196.1998261"},{"key":"29_CR5","doi-asserted-by":"publisher","first-page":"1048","DOI":"10.1016\/j.patcog.2010.11.010","volume":"44","author":"A. Bottino","year":"2011","unstructured":"Bottino, A., Laurentini, A.: A Nearly Optimal Algorithm for Covering the Interior of an Art Gallery. Pattern Recognition\u00a044, 1048\u20131056 (2011)","journal-title":"Pattern Recognition"},{"key":"29_CR6","unstructured":"Brod\u00e9n, B., Hammar, M., Nilsson, B.J.: Guarding Lines and 2-Link Polygons is APX-hard. In: 13th Canadian Conf.\u00a0on Computational Geometry, CCCG 2001, pp. 45\u201348 (2001)"},{"key":"29_CR7","first-page":"425","volume":"18","author":"M.C. Couto","year":"2011","unstructured":"Couto, M.C., Rezende, P.J., Souza, C.C.: An Exact Algorithm for Minimizing Vertex Guards on Art Galleries. Int.\u00a0T.\u00a0Oper.\u00a0Res.\u00a018, 425\u2013448 (2011)","journal-title":"Int.\u00a0T.\u00a0Oper.\u00a0Res."},{"key":"29_CR8","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0734-189X(84)80041-9","volume":"27","author":"H. Edelsbrunner","year":"1984","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Welzl, E.: Stationing Guards in Rectilinear Art Galleries. Computer Vision, Graphics, and Image Processing\u00a027, 167\u2013176 (1984)","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"29_CR9","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\u00a031, 79\u2013113 (2001)","journal-title":"Algorithmica"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.dam.2009.12.004","volume":"158","author":"S.K. Ghosh","year":"2010","unstructured":"Ghosh, S.K.: Approximation Algorithms for Art Gallery Problems in Polygons. Discrete Applied Mathematics\u00a0158, 718\u2013722 (2010)","journal-title":"Discrete Applied Mathematics"},{"key":"29_CR11","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1137\/0604020","volume":"4","author":"J. Kahn","year":"1983","unstructured":"Kahn, J., Klawe, M., Kleitman, D.: Traditional Galleries Require Fewer Watchmen. SIAM J. Algebraic and Discrete Methods\u00a04, 194\u2013206 (1983)","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.comgeo.2007.02.002","volume":"39","author":"M.J. Katz","year":"2008","unstructured":"Katz, M.J., Roisman, G.S.: On Guarding the Vertices of Rectilinear Domains. Comput.\u00a0Geom.\u00a0Theory Appl.\u00a039, 219\u2013228 (2008)","journal-title":"Comput.\u00a0Geom.\u00a0Theory Appl."},{"key":"29_CR13","unstructured":"Krohn, E., Nilsson, B.J.: The Complexity of Guarding Monotone Polygons. In: 24th Canadian Conf.\u00a0on Computational Geometry, CCCG 2012, pp. 167\u2013172 (2012)"},{"key":"29_CR14","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"D.T. Lee","year":"1986","unstructured":"Lee, D.T., Lin, A.K.: Computational Complexity of Art Gallery Problems. IEEE Transactions on Information Theory\u00a032, 276\u2013282 (1986)","journal-title":"IEEE Transactions on Information Theory"},{"key":"29_CR15","first-page":"102","volume":"6","author":"A.M. Martins","year":"2006","unstructured":"Martins, A.M., Bajuelos, A.L.: Vertex Guards in a Subclass of Orthogonal Polygons. Int.\u00a0J.\u00a0Computer Science and Network Security\u00a06, 102\u2013108 (2006)","journal-title":"Int.\u00a0J.\u00a0Computer Science and Network Security"},{"key":"29_CR16","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"1","author":"N. Megiddo","year":"1982","unstructured":"Megiddo, N., Tamir, A.: On the Complexity of Locating Facilities in the Plane. Oper.\u00a0Res.\u00a0Lett.\u00a01, 194\u2013197 (1982)","journal-title":"Oper.\u00a0Res.\u00a0Lett."},{"key":"29_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1362","DOI":"10.1007\/11523468_110","volume-title":"Automata, Languages and Programming","author":"B.J. Nilsson","year":"2005","unstructured":"Nilsson, B.J.: Approximate Guarding of Monotone and Rectilinear Polygons. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1362\u20131373. Springer, Heidelberg (2005)"},{"key":"29_CR18","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, Inc., New York (1987)"},{"key":"29_CR19","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, P., Optimization, M.: Approximation and Complexity Classes. Journal of Computer and System Sciences\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"29_CR20","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1002\/malq.19950410212","volume":"41","author":"D. Schuchardt","year":"1995","unstructured":"Schuchardt, D., Hecker, H.: Two NP-hard Problems for Ortho-Polygons. Math. Logiv Quart.\u00a041, 261\u2013267 (1995)","journal-title":"Math. Logiv Quart."},{"key":"29_CR21","doi-asserted-by":"crossref","unstructured":"Urrutia, J.: Art Gallery and Illumination Problems. In: Sack, J.-R., Urrutia, J. (eds.) Handbook on Computational Geometry. Elsevier, North-Holland (2000)","DOI":"10.1016\/B978-044482537-7\/50023-1"},{"key":"29_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-540-24767-8_13","volume-title":"Computational Science and Its Applications \u2013 ICCSA 2004","author":"A.P. Tom\u00e1s","year":"2004","unstructured":"Tom\u00e1s, A.P., Bajuelos, A.L.: Quadratic-Time Linear-Space Algorithms for Generating Orthogonal Polygons with a Given Number of Vertices. In: Lagan\u00e1, A., Gavrilova, M.L., Kumar, V., Mun, Y., Tan, C.J.K., Gervasi, O. (eds.) ICCSA 2004. LNCS, vol.\u00a03045, pp. 117\u2013126. Springer, Heidelberg (2004)"},{"key":"29_CR23","doi-asserted-by":"crossref","unstructured":"Tom\u00e1s, A.P.: Guarding Path Orthogonal Polygons. Internal report, DCC (2013)","DOI":"10.1007\/978-3-642-40164-0_29"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40164-0_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T01:37:25Z","timestamp":1557970645000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40164-0_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401633","9783642401640"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40164-0_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}