{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T06:53:56Z","timestamp":1672469636295},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"02n03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p> Let P be a polygon, possibly with holes. We define a witness set W to be a set of points in P such that if any (prospective) guard set G guards W, then it is guaranteed that G guards P. Not all polygons admit a finite witness set. If a finite minimal witness set exists, then it cannot contain any witness in the interior of P, all witnesses must lie on the boundary of P, and there can be at most one witness in the interior of every edge. We give an algorithm to compute a minimum size witness set for P in O(n<jats:sup>2<\/jats:sup> log n) time, if such a set exists, or to report the non-existence within the same time bounds. We also outline two algorithms that use a witness set for P to test whether a (prospective) guard set sees all points in P. <\/jats:p>","DOI":"10.1142\/s0218195906002002","type":"journal-article","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T08:53:13Z","timestamp":1146127993000},"page":"205-226","source":"Crossref","is-referenced-by-count":6,"title":["GUARDING ART GALLERIES BY GUARDING WITNESSES"],"prefix":"10.1142","volume":"16","author":[{"given":"KYUNG-YONG","family":"CHWA","sequence":"first","affiliation":[{"name":"Department of Computer Science, KAIST, 373-1 Guseong-dong Yuseong-gu, Daejeon, 305-701, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BYUNG-CHEOL","family":"JO","sequence":"additional","affiliation":[{"name":"Taff System, Co. Ltd., Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHRISTIAN","family":"KNAUER","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Freie Universit\u00e4t Berlin, Takustra\u00dfe 9, D-14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ESTHER","family":"MOET","sequence":"additional","affiliation":[{"name":"Department of Information &amp; Computing Sciences, Universiteit Utrecht, P. O. Box 80.089, 3508 TB Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"REN\u00c9","family":"VAN OOSTRUM","sequence":"additional","affiliation":[{"name":"Department of Information &amp; Computing Sciences, Universiteit Utrecht, P. O. Box 80.089, 3508 TB Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHAN-SU","family":"SHIN","sequence":"additional","affiliation":[{"name":"School of Electronics and Information Engineering, Hankuk University of Foreign Studies, Yongin, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90061-1"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2.3.253"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1017"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01937271"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322142"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140304"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80064-8"},{"key":"rf10","series-title":"The International Series of Monographs on Computer Science","volume-title":"Art Gallery Theorems and Algorithms","author":"O'Rourke J.","year":"1987"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1109\/5.163407"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50023-1"},{"key":"rf13","first-page":"73","volume":"28","author":"Yang T.-C.","journal-title":"J. Korean Inform. Sci. Technol."}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195906002002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:20:34Z","timestamp":1565176834000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195906002002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":12,"journal-issue":{"issue":"02n03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0218195906002002"],"URL":"https:\/\/doi.org\/10.1142\/s0218195906002002","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}