{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T06:43:40Z","timestamp":1740120220011,"version":"3.37.3"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1526406"],"award-info":[{"award-number":["CCF-1526406"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p> Given a set [Formula: see text] of [Formula: see text] points in the plane, how many universal guards are sometimes necessary and always sufficient to guard any simple polygon with vertex set [Formula: see text]? We call this problem a Universal Guard Problem and provide a spectrum of results. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of [Formula: see text] vertices, or to guard all polygons in a given set of [Formula: see text] polygons on an [Formula: see text]-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities. <\/jats:p>","DOI":"10.1142\/s0218195918600038","type":"journal-article","created":{"date-parts":[[2018,7,12]],"date-time":"2018-07-12T21:58:56Z","timestamp":1531432736000},"page":"129-160","source":"Crossref","is-referenced-by-count":0,"title":["Universal Guard Problems"],"prefix":"10.1142","volume":"28","author":[{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, 38106 Braunschweig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3143-6232","authenticated-orcid":false,"given":"Qian","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY 11794, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0152-2279","authenticated-orcid":false,"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY 11794, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Scheffer","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, 38106 Braunschweig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2018,7,12]]},"reference":[{"key":"S0218195918600038BIB001","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195910003451"},{"key":"S0218195918600038BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"S0218195918600038BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90061-1"},{"key":"S0218195918600038BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57155-8_252"},{"key":"S0218195918600038BIB006","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2011.00804.x"},{"key":"S0218195918600038BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.05.014"},{"key":"S0218195918600038BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9961-x"},{"key":"S0218195918600038BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90059-X"},{"key":"S0218195918600038BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.12.004"},{"key":"S0218195918600038BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50012-7"},{"key":"S0218195918600038BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9352-x"},{"key":"S0218195918600038BIB019","doi-asserted-by":"publisher","DOI":"10.1137\/100791506"},{"issue":"1","key":"S0218195918600038BIB020","first-page":"168","volume":"5","author":"Krohn E.","year":"2014","journal-title":"J. Comput. Geom."},{"issue":"1","key":"S0218195918600038BIB021","volume":"17","author":"Kr\u00f6ller A.","year":"2012","journal-title":"ACM J. Experimental Algorithmics"},{"key":"S0218195918600038BIB022","series-title":"The International Series of Monographs on Computer Science","volume-title":"Art Gallery Theorems and Algorithms","author":"O\u2019Rourke J.","year":"1987"},{"key":"S0218195918600038BIB023","doi-asserted-by":"publisher","DOI":"10.1109\/5.163407"},{"journal-title":"Optimization Online","year":"2013","author":"Tozoni D. C.","key":"S0218195918600038BIB024"},{"key":"S0218195918600038BIB025","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195907002264"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195918600038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T10:16:03Z","timestamp":1569320163000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195918600038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":18,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2018,7,12]]},"published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1142\/S0218195918600038"],"URL":"https:\/\/doi.org\/10.1142\/s0218195918600038","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}