{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T06:34:28Z","timestamp":1712471668228},"reference-count":29,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T00:00:00Z","timestamp":1207008000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":1933,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Geometry"],"published-print":{"date-parts":[[2008,4]]},"DOI":"10.1016\/j.comgeo.2007.02.002","type":"journal-article","created":{"date-parts":[[2007,3,1]],"date-time":"2007-03-01T21:29:55Z","timestamp":1172784595000},"page":"219-228","source":"Crossref","is-referenced-by-count":37,"title":["On guarding the vertices of rectilinear domains"],"prefix":"10.1016","volume":"39","author":[{"given":"Matthew J.","family":"Katz","sequence":"first","affiliation":[]},{"given":"Gabriel S.","family":"Roisman","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.comgeo.2007.02.002_bib001","unstructured":"A. Aggarwal, The art gallery theorem: Its variations, applications and algorithmic aspects, PhD thesis, Johns Hopkins University, 1984"},{"key":"10.1016\/j.comgeo.2007.02.002_bib002","unstructured":"B. Ben-Moshe, M.J. Katz, J.S.B. Mitchell, A constant-factor approximation algorithm for optimal terrain guarding, in: Proc. 16th ACM\u2013SIAM Sympos. on Discrete Algorithms, 2005, pp. 515\u2013524"},{"key":"10.1016\/j.comgeo.2007.02.002_bib003","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0925-7721(95)00034-8","article-title":"Guarding polyhedral terrains","volume":"7","author":"Bose","year":"1997","journal-title":"Comput. Geom. Theory Appl."},{"key":"10.1016\/j.comgeo.2007.02.002_bib004","unstructured":"B. Brod\u00e9n, M. Hammar, B.J. Nilsson, Guarding lines and 2-link polygons is APX-hard, in: Proc. 13th Canad. Conf. Comput. Geom., 2001, pp. 45\u201348"},{"key":"10.1016\/j.comgeo.2007.02.002_bib005","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02570718","article-title":"Almost optimal set covers in finite VC-dimension","volume":"14","author":"Br\u00f6nnimann","year":"1995","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/j.comgeo.2007.02.002_bib006","unstructured":"D.Z. Chen, V. Estivill-Castro, J. Urrutia, Optimal guarding of polygons and monotone chains, in: Proc. 7th Canad. Conf. Comput. Geom., 1995, pp. 133\u2013138"},{"key":"10.1016\/j.comgeo.2007.02.002_bib007","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","article-title":"A combinatorial theorem in plane geometry","volume":"18","author":"Chv\u00e1tal","year":"1975","journal-title":"Combinatorial Theory Series B"},{"key":"10.1016\/j.comgeo.2007.02.002_bib008","doi-asserted-by":"crossref","unstructured":"K.L. Clarkson, K.R. Varadarajan, Improved approximation algorithms for geometric set cover, in: Proc. 21st Annu. ACM Sympos. Comput. Geom., 2005, pp. 135\u2013141","DOI":"10.1145\/1064092.1064115"},{"key":"10.1016\/j.comgeo.2007.02.002_bib009","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","article-title":"On rigid circuit graphs","volume":"25","author":"Dirac","year":"1961","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"10.1016\/j.comgeo.2007.02.002_bib010","doi-asserted-by":"crossref","unstructured":"A. Efrat, S. Har-Peled, Locating guards in art galleries, in: 2nd IFIP International Conference on Theoretical Computer Science, 2002, pp. 181\u2013192","DOI":"10.1007\/978-0-387-35608-2_16"},{"key":"10.1016\/j.comgeo.2007.02.002_bib011","unstructured":"S.J. Eidenbenz, (In-)approximability of visibility problems on polygons and terrains, PhD thesis, ETH Z\u00fcrich, Switzerland, 2000"},{"key":"10.1016\/j.comgeo.2007.02.002_bib012","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s00453-001-0040-8","article-title":"Inapproximability results for guarding polygons and terrains","volume":"31","author":"Eidenbenz","year":"2001","journal-title":"Algorithmica"},{"key":"10.1016\/j.comgeo.2007.02.002_bib013","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"issue":"2","key":"10.1016\/j.comgeo.2007.02.002_bib014","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","article-title":"Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph","volume":"1","author":"Gavril","year":"1972","journal-title":"SIAM J. Computing"},{"key":"10.1016\/j.comgeo.2007.02.002_bib015","unstructured":"S.K. Ghosh, Approximation algorithms for art gallery problems, in: Proc. Canadian Inform. Process. Soc. Congress, 1987, pp. 429\u2013434"},{"key":"10.1016\/j.comgeo.2007.02.002_bib016","doi-asserted-by":"crossref","unstructured":"H. Gonz\u00e1lez-Banos, J.-C. Latombe, A randomized art-gallery algorithm for sensor placement, in: Proc. 17th Annual Symposium on Computational Geometry, 2001, pp. 232\u2013240","DOI":"10.1145\/378583.378674"},{"key":"10.1016\/j.comgeo.2007.02.002_bib017","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF01553883","article-title":"An optimal visibility graph algorithm for triangulated simple polygons","volume":"4","author":"Hershberger","year":"1989","journal-title":"Algorithmica"},{"key":"10.1016\/j.comgeo.2007.02.002_bib018","series-title":"Handbook of Computational Geometry","first-page":"491","article-title":"Polygon decomposition","author":"Keil","year":"2000"},{"key":"10.1016\/j.comgeo.2007.02.002_bib019","series-title":"Proc. LATIN","first-page":"629","article-title":"A 4-approximation algorithm for guarding 1.5-dimensional terrains","volume":"vol. 3887","author":"King","year":"2006"},{"key":"10.1016\/j.comgeo.2007.02.002_bib020","doi-asserted-by":"crossref","unstructured":"V.S.A. Kumar, S. Arya, H. Ramesh, Hardness of a set cover with intersection 1, in: Proc. 27th International Colloquium, ICALP, 2000, pp. 624\u2013635","DOI":"10.1007\/3-540-45022-X_53"},{"key":"10.1016\/j.comgeo.2007.02.002_bib021","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","article-title":"Computational complexity of art gallery problems","volume":"IT-32","author":"Lee","year":"1986","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/j.comgeo.2007.02.002_bib022","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","article-title":"On the complexity of locating linear facilities in the plane","volume":"1","author":"Megiddo","year":"1982","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/j.comgeo.2007.02.002_bib023","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0022-0000(90)90017-F","article-title":"Covering orthogonal polygons with star polygons: The perfect graph approach","volume":"40","author":"Motwani","year":"1990","journal-title":"Comput. Syst. Sci."},{"key":"10.1016\/j.comgeo.2007.02.002_bib024","doi-asserted-by":"crossref","unstructured":"B.J. Nilsson, Approximate guarding of monotone and rectilinear polygons, in: Proc. 32nd International Colloquium, ICALP, 2005, pp. 1362\u20131373","DOI":"10.1007\/11523468_110"},{"key":"10.1016\/j.comgeo.2007.02.002_bib025","article-title":"Art Gallery Theorems and Algorithms","author":"O'Rourke","year":"1987"},{"key":"10.1016\/j.comgeo.2007.02.002_bib026","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1109\/TIT.1983.1056648","article-title":"Some NP-hard polygon decomposition problems","volume":"IT-30","author":"O'Rourke","year":"1983","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"9","key":"10.1016\/j.comgeo.2007.02.002_bib027","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1109\/5.163407","article-title":"Recent results in art galleries","volume":"80","author":"Shermer","year":"1992","journal-title":"Proc. IEEE"},{"key":"10.1016\/j.comgeo.2007.02.002_bib028","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1002\/malq.19950410212","article-title":"Two NP-hard art-gallery problems for ortho-polygons","volume":"41","author":"Schuchardt","year":"1995","journal-title":"Mathematical Logic Quarterly"},{"key":"10.1016\/j.comgeo.2007.02.002_bib029","series-title":"Handbook of Computational Geometry","first-page":"973","article-title":"Art gallery and illumination problems","author":"Urrutia","year":"2000"}],"container-title":["Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0925772107000259?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0925772107000259?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T01:28:41Z","timestamp":1556155721000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0925772107000259"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,4]]}},"alternative-id":["S0925772107000259"],"URL":"https:\/\/doi.org\/10.1016\/j.comgeo.2007.02.002","relation":{},"ISSN":["0925-7721"],"issn-type":[{"value":"0925-7721","type":"print"}],"subject":[],"published":{"date-parts":[[2008,4]]}}}