{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:37:43Z","timestamp":1725543463296},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540357537"},{"type":"electronic","value":"9783540357551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_22","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T05:24:10Z","timestamp":1151299450000},"page":"220-231","source":"Crossref","is-referenced-by-count":1,"title":["On Guarding Rectilinear Domains"],"prefix":"10.1007","author":[{"given":"Matthew J.","family":"Katz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel S.","family":"Roisman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","unstructured":"Aggarwal, A.: The Art Gallery Theorem: Its Variations, Applications and Algorithmic Aspects. Ph.D. thesis, Johns Hopkins University (1984)"},{"key":"22_CR2","unstructured":"Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B.: A constant-factor approximation algorithm for optimal terrain guarding. In: Proc. 16th ACM-SIAM Sympos. on Discrete Algorithms, pp. 515\u2013524 (2005)"},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0925-7721(95)00034-8","volume":"7","author":"P. Bose","year":"1997","unstructured":"Bose, P., Shermer, T., Toussaint, G., Zhu, B.: Guarding polyhedral terrains. Comput. Geom. Theory Appl.\u00a07, 173\u2013185 (1997)","journal-title":"Comput. Geom. Theory Appl."},{"key":"22_CR4","unstructured":"Brod\u00e9n, B., Hammar, M., Nilsson, B.J.: Guarding lines and 2-link polygons is APX-hard. In: Proc. 13th Canad. Conf. Comput. Geom., pp. 45\u201348 (2001)"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"263","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.\u00a014, 263\u2013279 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"22_CR6","unstructured":"Chen, D.Z., Estivill-Castro, V., Urrutia, J.: Optimal guarding of polygons and monotone chains. In: Proc. 7th Canad. Conf. Comput. Geom., pp. 133\u2013138 (1995)"},{"key":"22_CR7","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. Combinatorial Theory Series B\u00a018, 39\u201341 (1975)","journal-title":"Combinatorial Theory Series B"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. In: Proc. 21st Annu. ACM Sympos. Comput. Geom., pp. 135\u2013141 (2005)","DOI":"10.1145\/1064092.1064115"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg\u00a025, 71\u201376 (1961)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Efrat, A., Har-Peled, S.: Locating guards in art galleries. In: 2nd IFIP International Conference on Theoretical Computer Science, pp. 181\u2013192 (2002)","DOI":"10.1007\/978-0-387-35608-2_16"},{"key":"22_CR11","unstructured":"Eidenbenz, S.J.: (In-)Approximability of Visibility Problems on Polygons and Terrains. Ph.D. thesis, ETH Z\u00fcrich, Switzerland (2000)"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00453-001-0040-8","volume":"31","author":"S.J. Eidenbenz","year":"2001","unstructured":"Eidenbenz, S.J., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica\u00a031, 79\u2013113 (2001)","journal-title":"Algorithmica"},{"key":"22_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"issue":"2","key":"22_CR14","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Computing\u00a01(2), 180\u2013187 (1972)","journal-title":"SIAM J. Computing"},{"key":"22_CR15","unstructured":"Ghosh, S.K.: Approximation algorithms for art gallery problems. In: Proc. Canadian Inform. Process. Soc. Congress, pp. 429\u2013434 (1987)"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Gonz\u00e1lez-Banos, H., Latombe, J.-C.: A randomized art-gallery algorithm for sensor placement. In: Proc. 17th Annual Symposium on Computational Geometry, pp. 232\u2013240 (2001)","DOI":"10.1145\/378583.378674"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/B978-044482537-7\/50012-7","volume-title":"Handbook of Computational Geometry","author":"J.M. Keil","year":"2000","unstructured":"Keil, J.M.: Polygon decomposition. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 491\u2013518. Elsevier Science Publishers B.V. North-Holland, Amsterdam (2000)"},{"key":"22_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1007\/3-540-45022-X_53","volume-title":"Automata, Languages and Programming","author":"V.S.A. Kumar","year":"2000","unstructured":"Kumar, V.S.A., Arya, S., Ramesh, H.: Hardness of a set cover with intersection 1. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 624\u2013635. Springer, Heidelberg (2000)"},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"IT-32","author":"D.T. Lee","year":"1986","unstructured":"Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inform. Theory\u00a0IT-32, 276\u2013282 (1986)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"22_CR20","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 linear facilities in the plane. Oper. Res. Lett.\u00a01, 194\u2013197 (1982)","journal-title":"Oper. Res. Lett."},{"key":"22_CR21","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0022-0000(90)90017-F","volume":"40","author":"R. Motwani","year":"1990","unstructured":"Motwani, R., Raghunathan, A., Saran, H.: Covering orthogonal polygons with star polygons: The perfect graph approach. Comput. Syst. Sci.\u00a040, 19\u201348 (1990)","journal-title":"Comput. Syst. Sci."},{"key":"22_CR22","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":"22_CR23","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)"},{"key":"22_CR24","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1109\/TIT.1983.1056648","volume":"IT-30","author":"J. O\u2019Rourke","year":"1983","unstructured":"O\u2019Rourke, J., Supowit, K.J.: Some NP-hard polygon decomposition problems. IEEE Trans. Inform. Theory\u00a0IT-30, 181\u2013190 (1983)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"9","key":"22_CR25","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1109\/5.163407","volume":"80","author":"T.C. Shermer","year":"1992","unstructured":"Shermer, T.C.: Recent results in art galleries. Proc. IEEE\u00a080(9), 1384\u20131399 (1992)","journal-title":"Proc. IEEE"},{"key":"22_CR26","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. Mathematical Logic Quarterly\u00a041, 261\u2013267 (1995)","journal-title":"Mathematical Logic Quarterly"},{"key":"22_CR27","doi-asserted-by":"publisher","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. 973\u20131027. Elsevier Science Publishers B.V., North-Holland, Amsterdam (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:19:17Z","timestamp":1619507957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/11785293_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}