{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:39:10Z","timestamp":1758274750828},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602200"},{"type":"electronic","value":"9783540447474"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_56","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:52:24Z","timestamp":1330278744000},"page":"122-134","source":"Crossref","is-referenced-by-count":5,"title":["Computing a shortest watchman path in a simple polygon in polynomial-time"],"prefix":"10.1007","author":[{"given":"Svante","family":"Carlsson","sequence":"first","affiliation":[]},{"given":"H\u00e5kan","family":"Jonsson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"11_CR1","unstructured":"A. Aggarwal. The Art Gallery Theorem: Its variations, applications and algorithmic aspects. PhD thesis, John Hopkins University, 1984."},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"B. K. Bhattacharya, A. Mukhopadhyay, and G. T. Toussaint. A linear time alogorithm for computing the shortest line segment from which a polygon is weakly externally visible. In Proceedings of 2nd WADS, pages 412\u2013424. Springer-Verlag, 1991.","DOI":"10.1007\/BFb0028280"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"S. Carlsson, H. Jonsson, and B. J. Nilsson. Finding the shortest watchman route in a simple polygon. In Proceedings of ISAAC'93, pages 58\u201367. Springer-Verlag, 1993. LNCS 762.","DOI":"10.1007\/3-540-57568-5_235"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle. Triangulating a simple polygon in linear time. In Proceedings of the 31th Symposium on Foundations of Computer Science, pages 220\u2013230, 1990.","DOI":"10.1109\/FSCS.1990.89541"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0020-0190(88)90141-X","volume":"28","author":"W. Chin","year":"1988","unstructured":"W. Chin and S. Ntafos. Optimum watchman routes. Inform. Process. Lett., 28:39\u201344, 1988.","journal-title":"Inform. Process. Lett."},{"key":"11_CR6","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF02574671","volume":"6","author":"W. Chin","year":"1991","unstructured":"W. Chin and S. Ntafos. Shortest watchman routes in simple polygons. Disc. Comp. Geometry, 6:9\u201331, 1991.","journal-title":"Disc. Comp. Geometry"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0020-0255(92)90072-G","volume":"63","author":"W. Chin","year":"1992","unstructured":"W. Chin and S. Ntafos. The zookeeper route problem. Inform. Sci., 63:245\u2013259, 1992.","journal-title":"Inform. Sci."},{"key":"11_CR8","unstructured":"J. Czyzowicz, P. Egyed, H. Everett, D. Rappaport, T. Shermer, D. Souvaine, G. Toussaint, and J. Urrutia. The aquarium keeper's problem. In Proceedings of the 2nd ACM-SIAM Symposium on Discrete Algorithms, pages 459\u2013464, 1991."},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"G. Das, P. J. Heffernan, and G. Narasimhan. Finding all weakly-visible chords of a polygon in linear time. In Proceedings of the 4th Scandinavian Workshop on Algorithm Theory (SWAT'94), pages 119\u2013130. Springer-Verlag, 1994. LNCS 824.","DOI":"10.1007\/3-540-58218-5_11"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"G. Das and G. Narasimhan. Optimal linear-time algorithm for the shortest illuminating line segment in a polygon. In Proceedings of the 10th Annual Symposium on Computational Geometry, pages 259\u2013266, 1994.","DOI":"10.1145\/177424.177984"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"J. Forsberg, U. Larsson, and \u00c5. Wernersson. On mobile robot navigation in cluttered rooms using the range weighted hough transform. IEEE Robotics and Automation Society Magazine, 1995. Department of Computer Science and Electrical Engineering, Lule\u00e5 University of Technology. Accepted for publication in the special issue on mobile robots.","DOI":"10.1109\/100.388295"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L. Guibas","year":"1987","unstructured":"L. Guibas, J. Hersberger, D. Leven, M. Sharir, and R. Tarjan. Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209\u2013233, 1987.","journal-title":"Algorithmica"},{"key":"11_CR13","first-page":"104","volume-title":"An efficient solution to the zookeeper's problem","author":"J. Hersberger","year":"1994","unstructured":"J. Hersberger and J. Snoeyink. An efficient solution to the zookeeper's problem. In Proceedings of the 6th Canadian Conference on Computational Geometry, pages 104\u2013109, 1994. U. of Saskatchewan, Saskatoon, Ontario."},{"key":"11_CR14","unstructured":"J. Hersberger and S. Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, pages 54\u201363, 1993."},{"volume-title":"Robot Motion Planning","year":"1991","key":"11_CR15","unstructured":"J.-C. Latombe, editor. Robot Motion Planning. Kluwer Academic Publishers, Norwell, MA, 1991."},{"issue":"2","key":"11_CR16","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"D.T. Lee","year":"1986","unstructured":"D.T. Lee and A.K. Lin. Computational complexity of art gallery problems. IEEE Trans. Info. Theory, 32(2):276\u2013282, 1986.","journal-title":"IEEE Trans. Info. Theory"},{"key":"11_CR17","volume-title":"PhD thesis","author":"B. Nilsson","year":"1995","unstructured":"B. Nilsson. Guarding Art Galleries; Methods for Mobile Guards. PhD thesis, Lund University, Sweden, 1995."},{"key":"11_CR18","unstructured":"J. O'Rourke. Art Gallery Theorems and Algorithms. Oxford univ. press, 1987. ISBN 0-19-503965-3."},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"1213","DOI":"10.1109\/12.59852","volume":"39","author":"J.-R. Sack","year":"1990","unstructured":"J.-R. Sack and S. Suri. An optimal algorithm for detecting weak visibility. IEEE Trans. Comput., 39:1213\u20131219, 1990.","journal-title":"IEEE Trans. Comput."},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"T. Shermer. Recent results in art galleries. In Proceedings of the IEEE, pages 1384\u20131399, September 1992.","DOI":"10.1109\/5.163407"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"X.-H. Tan, T. Hirata, and Y. Inagaki. An incremental algorithm for constructing shortest watchman routes. In Proceedings of ISA'91, pages 163\u2013175. Springer-Verlag, 1991. LNCS 557.","DOI":"10.1007\/3-540-54945-5_60"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"X.-H. Tan, T. Hirata, and Y. Inagaki. Constructing shortest watchman routes by divide-and-conquer. In Proceedings of ISAAC'93, pages 68\u201377. Springer-Verlag, 1993. LNCS 762.","DOI":"10.1007\/3-540-57568-5_236"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:56:08Z","timestamp":1605646568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}