{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T10:07:41Z","timestamp":1768730861917,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540697329","type":"print"},{"value":"9783540697336","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69733-6_59","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"600-610","source":"Crossref","is-referenced-by-count":0,"title":["On Some City Guarding Problems"],"prefix":"10.1007","author":[{"given":"Lichen","family":"Bao","sequence":"first","affiliation":[]},{"given":"Sergey","family":"Bereg","sequence":"additional","affiliation":[]},{"given":"Ovidiu","family":"Daescu","sequence":"additional","affiliation":[]},{"given":"Simeon","family":"Ntafos","sequence":"additional","affiliation":[]},{"given":"Junqiang","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"59_CR1","unstructured":"Aggarwal, A.: The Art Gallery Theorem: Its Variations, Applications, and Algorithmic Aspects. Ph.D. thesis, Johns Hopkins University, Baltimore (1984)"},{"key":"59_CR2","unstructured":"Bao, L., Bereg, S., Daescu, O., Ntafos, S., Zhou, J.: The Complexity Study of City Guard Problem. The University of Texas at Dallas (manuscript, 2007)"},{"key":"59_CR3","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 Plan Geometry. J. Combin. Theory Ser. B\u00a018, 39\u201341 (1975)","journal-title":"J. Combin. Theory Ser. B"},{"key":"59_CR4","volume-title":"Computers and Intractability","author":"R. Garey","year":"1979","unstructured":"Garey, R., Johnson, D.: Computers and Intractability. W.H. Freeman, New York (1979)"},{"key":"59_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/BFb0032069","volume-title":"Automata, Languages and Programming","author":"F. Hoffmann","year":"1990","unstructured":"Hoffmann, F.: On the Rectilinear Art Gallery Problem. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol.\u00a0443, pp. 717\u2013728. Springer, Heidelberg (1990)"},{"issue":"2","key":"59_CR6","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0895480194265611","volume":"9","author":"F. Hoffmann","year":"1996","unstructured":"Hoffmann, F., Kriegel, K.: A Graph Coloring Result and Its Consequences for Polygon Guarding Problems. SIAM J. Discrete Mathematics\u00a09(2), 210\u2013224 (1996)","journal-title":"SIAM J. Discrete Mathematics"},{"key":"59_CR7","unstructured":"Hoffmann, F., Kriegel, K., T\u00f3th, C.D.: Vertex Guards in Reclinear Polygons with Holes. In: Hoffmann, F., Kriegel, K., T\u00f3th, C.D. (eds.) Kyoto International Conference on Computational Geometry and Graph Theory (2007)"},{"key":"59_CR8","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":"59_CR9","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. Inform. Theory\u00a032, 276\u2013282 (1986)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"59_CR10","unstructured":"Lenhart, W., Jennings, G.: An Art Gallery Theorem for Line Segments in the Plane, Williams College (manuscript, 1990)"},{"key":"59_CR11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(86)90050-5","volume":"23","author":"S. Ntafos","year":"1986","unstructured":"Ntafos, S.: On Gallery Watchman in Grid. Info. Proc. Let.\u00a023, 99\u2013102 (1986)","journal-title":"Info. Proc. Let."},{"key":"59_CR12","first-page":"560","volume":"22","author":"T. Lozano-P\u0107rez","year":"1979","unstructured":"Lozano-P\u0107rez, T., Wesley, M.: An Algorithm for Planning Collision-Free Paths among Polyhedral Obstacles. Commun. Ass. Comput. Mach.\u00a022, 560\u2013570 (1979)","journal-title":"Commun. Ass. Comput. Mach."},{"key":"59_CR13","unstructured":"Lubiw, A.: Orderings and Some Combinatorial Optimization Problems with Geometric Applications. Ph.D. thesis, University of Toronto (1985)"},{"key":"59_CR14","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/BF00146907","volume":"14","author":"J. O\u2019Rourke","year":"1983","unstructured":"O\u2019Rourke, J.: Galleries need Fewer Mobile Guards: A Variation on Chvatal\u2019s Theorem. Geometriae Dedicata\u00a014, 273\u2013283 (1983)","journal-title":"Geometriae Dedicata"},{"key":"59_CR15","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/BF01918136","volume":"21","author":"J. O\u2019Rourke","year":"1983","unstructured":"O\u2019Rourke, J.: An Alternate Proof of the Rectitlinear Art Gallery Theorem. J. of Geometry\u00a021, 118\u2013130 (1983)","journal-title":"J. of Geometry"},{"key":"59_CR16","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, Oxford (1987)"},{"key":"59_CR17","unstructured":"O\u2019Rourke, J.: Recovery of Convexity from Visibility Graphs. Tech. Rep. 90.4.6, Dept. Computer Science, Smith College (1990)"},{"key":"59_CR18","unstructured":"Shermer, T.: Recent Results in Art Galleries. Tech Report CMPT TR 90-10, Simon Fraser University, Computing Science (1990)"},{"key":"59_CR19","volume-title":"Handbook on Computational Geometry","author":"J. Urrutia","year":"2000","unstructured":"Urrutia, J.: Art Gallery and Illumination Problems. In: Sack, J.R., Urrutia, J. (eds.) Handbook on Computational Geometry. Elsevier, Amsterdam (2000)"},{"key":"59_CR20","doi-asserted-by":"crossref","unstructured":"Zylinski, P.: Orthogonal Art Galleries with Holes: a Coloring Proof of Aggarwal\u2019s Theorem. The electronic Journal of Combinatorics\u00a013 (2006)","DOI":"10.37236\/1046"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69733-6_59.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:02:22Z","timestamp":1605762142000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69733-6_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540697329","9783540697336"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69733-6_59","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}