{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T08:55:31Z","timestamp":1760345731597},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1993,3]]},"abstract":"<jats:p> A watchman, in the terminology of art galleries, is a mobile guard. We consider several watchman and guard problems for different classes of polygons. We introduce the notion of vision spans along a path or route which provide a natural connection between the art gallery problem, the m-watchmen routes problem and the watchman route problem. <\/jats:p><jats:p> We prove that finding the minimum number of vision points, i.e., static guards, along a shortest watchman route is NP-hard. We provide a linear time algorithm to compute the best set of static guards in a histogram polygon. The m-watchmen routes problem, minimize total length of routes for m watchmen, is NP-hard for simple polygons. We give a \u0398(n<jats:sup>3<\/jats:sup>+n<jats:sup>2<\/jats:sup>m<jats:sup>2<\/jats:sup>)-time algorithm to compute the best set of m watchmen in a histogram. <\/jats:p>","DOI":"10.1142\/s0218195993000063","type":"journal-article","created":{"date-parts":[[2004,11,23]],"date-time":"2004-11-23T03:29:30Z","timestamp":1101180570000},"page":"85-105","source":"Crossref","is-referenced-by-count":22,"title":["OPTIMUM GUARD COVERS AND m-WATCHMEN ROUTES FOR RESTRICTED POLYGONS"],"prefix":"10.1142","volume":"03","author":[{"given":"SVANTE","family":"CARLSSON","sequence":"first","affiliation":[{"name":"Department of Computer Science, Lule\u00e5 University of Technology 951 87 Lule\u00e5, Sweden"}]},{"given":"BENGT J.","family":"NILSSON","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lun\u00e5 University, Box 118, 221 00 Lund, Sweden"}]},{"given":"SIMEON","family":"NTAFOS","sequence":"additional","affiliation":[{"name":"Computer Science Program, University of Texas at Dallas, Richardson, TX 75083\u20130688, U.S.A."}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195993000063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T23:57:37Z","timestamp":1565135857000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195993000063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1993,3]]}},"alternative-id":["10.1142\/S0218195993000063"],"URL":"https:\/\/doi.org\/10.1142\/s0218195993000063","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}