{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:24:40Z","timestamp":1760441080580},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,5,9]],"date-time":"2012-05-09T00:00:00Z","timestamp":1336521600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1007\/s00454-012-9429-1","type":"journal-article","created":{"date-parts":[[2012,5,8]],"date-time":"2012-05-08T09:30:09Z","timestamp":1336469409000},"page":"711-720","source":"Crossref","is-referenced-by-count":14,"title":["The Art Gallery Theorem for Polyominoes"],"prefix":"10.1007","volume":"48","author":[{"given":"Therese","family":"Biedl","sequence":"first","affiliation":[]},{"given":"Mohammad T.","family":"Irfan","sequence":"additional","affiliation":[]},{"given":"Justin","family":"Iwerks","sequence":"additional","affiliation":[]},{"given":"Joondong","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,5,9]]},"reference":[{"issue":"5","key":"9429_CR1","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1142\/S0218195910003451","volume":"20","author":"Y. Amit","year":"2010","unstructured":"Amit, Y., Mitchell, J.S.B., Packer, E.: Locating guards for visibility coverage of polygons. Int. J. Comput. Geom. Appl. 20(5), 601\u2013630 (2010)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9429_CR2","doi-asserted-by":"crossref","first-page":"1631","DOI":"10.1137\/S0097539704446384","volume":"36","author":"B. Ben-Moshe","year":"2007","unstructured":"Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B.: A constant-factor approximation algorithm for optimal terrain guarding. SIAM J. Comput. 36, 1631\u20131647 (2007)","journal-title":"SIAM J. Comput."},{"key":"9429_CR3","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1145\/1998196.1998261","volume-title":"Proc. 27th Annual Symposium on Computational Geometry (SoCG 2011)","author":"T. Biedl","year":"2011","unstructured":"Biedl, T., Irfan, M.T., Iwerks, J., Kim, J., Mitchell, J.S.B.: Guarding polyominoes. In: Proc. 27th Annual Symposium on Computational Geometry (SoCG 2011), pp.\u00a0387\u2013396 (2011)"},{"key":"9429_CR4","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF02574029","volume":"13","author":"I. Bjorling-Sachs","year":"1995","unstructured":"Bjorling-Sachs, I., Souvaine, D.: An efficient algorithm for placing guards in polygons with holes. Discrete Comput. Geom. 13, 77\u2013109 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"9429_CR5","doi-asserted-by":"crossref","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":"9429_CR6","first-page":"429","volume-title":"Proc. of Canadian Information Processing Society Congress","author":"S. Ghosh","year":"1987","unstructured":"Ghosh, S.: Approximation algorithms for art gallery problems. In: Proc. of Canadian Information Processing Society Congress, pp.\u00a0429\u2013434 (1987)"},{"issue":"6","key":"9429_CR7","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1016\/j.dam.2009.12.004","volume":"158","author":"S. Ghosh","year":"2010","unstructured":"Ghosh, S.: Approximation algorithms for art gallery problems in polygons. Discrete Appl. Math. 158(6), 718\u2013722 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9429_CR8","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1137\/0607051","volume":"7","author":"E. Gy\u00f6ri","year":"1986","unstructured":"Gy\u00f6ri, E.: A short proof of the rectilinear art gallery theorem. SIAM J. Algebr. Discrete Methods 7(3), 452\u2013454 (1986)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9429_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/BFb0032069","volume-title":"Proc. 17th International Colloquium on Automata, Languages and Programming","author":"F. Hoffman","year":"1990","unstructured":"Hoffman, F.: On the rectilinear art gallery problem. In: Proc. 17th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol.\u00a0443, pp.\u00a0717\u2013728. Springer, Berlin (1990)"},{"issue":"2","key":"9429_CR10","doi-asserted-by":"crossref","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. Algebr. Discrete Methods 4(2), 194\u2013206 (1983)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"3","key":"9429_CR11","doi-asserted-by":"crossref","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. Geom. 39(3), 219\u2013228 (2008)","journal-title":"Comput. Geom."},{"issue":"2","key":"9429_CR12","doi-asserted-by":"crossref","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 Trans. Inf. Theory 32(2), 276\u2013282 (1986)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9429_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1362","DOI":"10.1007\/11523468_110","volume-title":"Proc. 32nd International Colloquium on Automata, Languages and Programming","author":"B.J. Nilsson","year":"2005","unstructured":"Nilsson, B.J.: Approximate guarding of monotone and rectilinear polygons. In: Proc. 32nd International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol.\u00a03580, pp.\u00a01362\u20131373. Springer, Berlin (2005)"},{"issue":"1","key":"9429_CR14","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/BF01918136","volume":"21","author":"J. O\u2019Rourke","year":"1983","unstructured":"O\u2019Rourke, J.: An alternate proof of the rectilinear art gallery theorem. J. Geom. 21(1), 118\u2013130 (1983)","journal-title":"J. Geom."},{"key":"9429_CR15","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., Oxford (1987)"},{"key":"9429_CR16","first-page":"137","volume-title":"Proc. of the Cologne\u2013Twente Workshop on Graphs and Combinatorial Optimizations (CTW 2010)","author":"V. Pinciu","year":"2010","unstructured":"Pinciu, V.: Pixel guards in polyominoes. In: Proc. of the Cologne\u2013Twente Workshop on Graphs and Combinatorial Optimizations (CTW 2010), pp.\u00a0137\u2013140 (2010)"},{"issue":"2","key":"9429_CR17","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. Log. Q. 41(2), 261\u2013267 (1995)","journal-title":"Math. Log. Q."},{"issue":"9","key":"9429_CR18","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1109\/5.163407","volume":"80","author":"T. Shermer","year":"1992","unstructured":"Shermer, T.: Recent results in art galleries. Proc. IEEE 80(9), 1384\u20131399 (1992)","journal-title":"Proc. IEEE"},{"key":"9429_CR19","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1016\/B978-044482537-7\/50023-1","volume-title":"Handbook of Computational Geometry","author":"J. Urrutia","year":"2000","unstructured":"Urrutia, J.: Art gallery and illumination problems. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp.\u00a0973\u20131027. Elsevier, Amsterdam (2000)"},{"issue":"2","key":"9429_CR20","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1142\/S0218195907002264","volume":"17","author":"C. Worman","year":"2007","unstructured":"Worman, C., Keil, J.M.: Polygon decomposition and the orthogonal art gallery problem. Int. J. Comput. Geom. Appl. 17(2), 105\u2013138 (2007)","journal-title":"Int. J. Comput. Geom. Appl."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9429-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-012-9429-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9429-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:50:35Z","timestamp":1559073035000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-012-9429-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,9]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["9429"],"URL":"https:\/\/doi.org\/10.1007\/s00454-012-9429-1","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,9]]}}}