{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T05:51:58Z","timestamp":1725688318193},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642311543"},{"type":"electronic","value":"9783642311550"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_4","type":"book-chapter","created":{"date-parts":[[2012,6,13]],"date-time":"2012-06-13T02:21:27Z","timestamp":1339554087000},"page":"36-47","source":"Crossref","is-referenced-by-count":2,"title":["Watchman Routes for Lines and Segments"],"prefix":"10.1007","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[]},{"given":"Pawe\u0142","family":"\u017byli\u0144ski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"15","key":"4_CR1","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1016\/j.tcs.2010.08.014","volume":"412","author":"V.E. Brimkov","year":"2011","unstructured":"Brimkov, V.E., Leach, A., Mastroianni, M., Wu, J.: Guarding a set of line segments in the plane. Theoretical Computer Science\u00a0412(15), 1313\u20131324 (2011)","journal-title":"Theoretical Computer Science"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Chin, W., Ntafos, S.: Optimum watchman routes. In: Proc. 2nd Symposium on Computational Geometry, pp. 24\u201333 (1986)","DOI":"10.1145\/10515.10518"},{"issue":"1","key":"4_CR3","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0020-0190(88)90141-X","volume":"28","author":"W. Chin","year":"1988","unstructured":"Chin, W., Ntafos, S.: Optimum watchman routes. Information Processing Letters\u00a028(1), 39\u201344 (1988)","journal-title":"Information Processing Letters"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V. Chv\u00e1tal","year":"1997","unstructured":"Chv\u00e1tal, V.: A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Series B\u00a018, 39\u201341 (1997)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Dror, M., Efrat, A., Lubiw, A., Mitchell, J.S.B.: Touring a sequence of polygons. In: Proc. 35th Symposium on Theory of Computing, pp. 473\u2013482 (2003)","DOI":"10.1145\/780611.780612"},{"issue":"1","key":"4_CR6","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0196-6774(03)00047-6","volume":"48","author":"A. Dumitrescu","year":"2003","unstructured":"Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. Journal of Algorithms\u00a048(1), 135\u2013159 (2003)","journal-title":"Journal of Algorithms"},{"issue":"7","key":"4_CR7","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1016\/j.comgeo.2012.02.001","volume":"45","author":"A. Dumitrescu","year":"2012","unstructured":"Dumitrescu, A., T\u00f3th, C.D.: Watchman tours for polygons with holes. Computational Geometry: Theory and Applications\u00a045(7), 326\u2013333 (2012)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proc. 35th ACM Symposium on Theory of Computing, pp. 448\u2013455 (2003)","DOI":"10.1145\/780606.780608"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Graham, R., Johnson, D.S.: Some NP-complete geometric problems. In: Proc. 8th ACM Symposium on Theory of Computing, pp. 10\u201322 (1976)","DOI":"10.1145\/800113.803626"},{"key":"4_CR10","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 Co., New York (1979)"},{"issue":"6","key":"4_CR11","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0925-7721(93)90013-V","volume":"2","author":"L.P. Gewali","year":"1993","unstructured":"Gewali, L.P., Ntafos, S.: Covering grids and orthogonal polygons with periscope guards. Computational Geometry: Theory and Applications\u00a02(6), 309\u2013334 (1993)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"4_CR12","unstructured":"Hoffmann, F.: Private communication. In: The European Workshop on Computational Geometry (EuroCG 2000), Eilat, Israel (2000)"},{"issue":"2","key":"4_CR13","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.comgeo.2006.11.002","volume":"37","author":"A. Kosowski","year":"2007","unstructured":"Kosowski, A., Ma\u0142afiejski, M., \u017byli\u0144ski, P.: Cooperative mobile guards in grids. Computational Geometry: Theory and Applications\u00a037(2), 59\u201371 (2007)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Mata, C.S., Mitchell, J.S.B.: Approximation algorithms for geometric tour and network design problems. In: Proc. 11th Symposium on Computational Geometry, pp. 360\u2013369 (1995)","DOI":"10.1145\/220279.220318"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 633\u2013701. Elsevier (2000)","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"key":"4_CR16","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 watchmen in grids. Information Processing Letters\u00a023, 99\u2013102 (1986)","journal-title":"Information Processing Letters"},{"key":"4_CR17","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, New York (1987)"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C.H. Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: Euclidean TSP is NP-complete. Theoretical Computer Science\u00a04, 237\u2013244 (1977)","journal-title":"Theoretical Computer Science"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1109\/5.163407","volume":"80","author":"T. Shermer","year":"1992","unstructured":"Shermer, T.: Recent results in Art Galleries. Proc. of the IEEE\u00a080, 1384\u20131399 (1992)","journal-title":"Proc. of the IEEE"},{"key":"4_CR20","unstructured":"Slavik, P.: The errand scheduling problem, CSE Technical Report 97-02, University of Buffalo (1997)"},{"issue":"1","key":"4_CR21","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0020-0190(00)00146-0","volume":"77","author":"X. Tan","year":"2001","unstructured":"Tan, X.: Fast computation of shortest watchman routes in simple polygons. Information Processing Letters\u00a077(1), 27\u201333 (2001)","journal-title":"Information Processing Letters"},{"issue":"1","key":"4_CR22","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2007.05.021","volume":"384","author":"X. Tan","year":"2007","unstructured":"Tan, X.: A linear-time 2-approximation algorithm for the watchman route problem for simple polygons. Theoretical Computer Science\u00a0384(1), 92\u2013103 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"4_CR23","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0925-7721(01)00057-8","volume":"21","author":"C.D. T\u00f3th","year":"2002","unstructured":"T\u00f3th, C.D.: Illumination in the presence of opaque line segments in the plane. Computational Geometry: Theory and Applications\u00a021(3), 193\u2013204 (2002)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"3","key":"4_CR24","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00454-003-2797-9","volume":"30","author":"C.D. T\u00f3th","year":"2003","unstructured":"T\u00f3th, C.D.: Illuminating disjoint line segments in the plane. Discrete & Computational Geometry\u00a030(3), 489\u2013505 (2003)","journal-title":"Discrete & Computational Geometry"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Urrutia, J.: Art gallery and illumination problems. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 973\u20131027. Elsevier (2000)","DOI":"10.1016\/B978-044482537-7\/50023-1"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Xu, N., Brass, P.: On the complexity of guarding problems on orthogonal arrangements. In: Abstracts of the 20th Fall Workshop on Computational Geometry (FWCG 2010), #33 (2010)","DOI":"10.1142\/S0218195910003323"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:48:39Z","timestamp":1620128919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}