{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:23:14Z","timestamp":1760440994162},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,5,6]],"date-time":"2011-05-06T00:00:00Z","timestamp":1304640000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s00454-011-9352-x","type":"journal-article","created":{"date-parts":[[2011,5,5]],"date-time":"2011-05-05T18:14:09Z","timestamp":1304619249000},"page":"252-269","source":"Crossref","is-referenced-by-count":22,"title":["Improved Approximation for Guarding Simple Galleries from the Perimeter"],"prefix":"10.1007","volume":"46","author":[{"given":"James","family":"King","sequence":"first","affiliation":[]},{"given":"David","family":"Kirkpatrick","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,5,6]]},"reference":[{"key":"9352_CR1","unstructured":"Aggarwal, A.: The art gallery theorem: its variations, applications and algorithmic aspects. Ph.D. thesis, The Johns Hopkins University, Baltimore, MD (1984)"},{"issue":"7","key":"9352_CR2","doi-asserted-by":"crossref","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B. Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size \u03b5-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248\u20133282 (2010)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9352_CR3","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4), 929\u2013965 (1989)","journal-title":"J. ACM"},{"issue":"3","key":"9352_CR4","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0925-7721(01)00070-0","volume":"23","author":"P. Bose","year":"2002","unstructured":"Bose, P., Lubiw, A., Munro, J.I.: Efficient visibility queries in simple polygons. Comput. Geom. Theory Appl. 23(3), 313\u2013335 (2002)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"9352_CR5","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(1), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9352_CR6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"9352_CR7","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/978-3-540-73951-7_15","volume-title":"Proc. 10th Workshop on Algorithms and Data Structures","author":"A. Deshpande","year":"2007","unstructured":"Deshpande, A., Kim, T., Demaine, E.D., Sarma, S.E.: A pseudopolynomial time O(log\u2009n)-approximation algorithm for art gallery problems. In: Proc. 10th Workshop on Algorithms and Data Structures, Halifax, Canada, pp. 163\u2013174 (2007)"},{"issue":"6","key":"9352_CR8","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1016\/j.ipl.2006.05.014","volume":"100","author":"A. Efrat","year":"2006","unstructured":"Efrat, A., Har-Peled, S.: Guarding galleries and terrains. Inf. Process. Lett. 100(6), 238\u2013245 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9352_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/3-540-49381-6_45","volume-title":"Proc. 9th Int. Symp. Algorithms and Computation","author":"S. Eidenbenz","year":"1998","unstructured":"Eidenbenz, S.: Inapproximability results for guarding polygons without holes. In: Proc. 9th Int. Symp. Algorithms and Computation. Lecture Notes in Computer Science, vol. 1533, pp. 427\u2013436 (1998)"},{"issue":"1","key":"9352_CR10","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s00453-001-0040-8","volume":"31","author":"S. Eidenbenz","year":"2001","unstructured":"Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31(1), 79\u2013113 (2001)","journal-title":"Algorithmica"},{"issue":"4","key":"9352_CR11","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln\u2009n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9352_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"9352_CR13","first-page":"429","volume-title":"Proc. Canadian Information Processing Society Congress","author":"S. Ghosh","year":"1987","unstructured":"Ghosh, S.: Approximation algorithms for art gallery problems. In: Proc. Canadian Information Processing Society Congress, pp. 429\u2013436 (1987)"},{"issue":"1","key":"9352_CR14","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF02760925","volume":"101","author":"G. Kalai","year":"1997","unstructured":"Kalai, G., Matou\u0161ek, J.: Guarding galleries where every point sees a large area. Isr. J. Math. 101(1), 125\u2013139 (1997)","journal-title":"Isr. J. Math."},{"key":"9352_CR15","first-page":"27","volume-title":"Proc. 20th Canadian Conference on Computational Geometry","author":"J. King","year":"2008","unstructured":"King, J.: VC-dimension of visibility on terrains. In: Proc. 20th Canadian Conference on Computational Geometry, Montreal, Canada, pp. 27\u201330 (2008)"},{"issue":"1","key":"9352_CR16","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF02187833","volume":"7","author":"J. Koml\u00f3s","year":"1992","unstructured":"Koml\u00f3s, J., Pach, J., Woeginger, G.: Almost tight bounds for \u03b5-nets. Discrete Comput. Geom. 7(1), 163\u2013173 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"9352_CR17","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"32","author":"D. Lee","year":"1986","unstructured":"Lee, D., Lin, A.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32, 276\u2013282 (1986)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9352_CR18","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, London (1987)"},{"issue":"2","key":"9352_CR19","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1109\/TIT.1983.1056648","volume":"29","author":"J. O\u2019Rourke","year":"1983","unstructured":"O\u2019Rourke, J., Supowit, K.J.: Some NP-hard polygon decomposition problems. IEEE Trans. Inf. Theory 29(2), 181\u2013189 (1983)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9352_CR20","first-page":"475","volume-title":"Proc. 29th ACM Symp. Theory of Computing","author":"R. Raz","year":"1997","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree-test and a sub-constant error-probability PCP characterization of NP. In: Proc. 29th ACM Symp. Theory of Computing. El Paso, TX, pp. 475\u2013484 (1997)"},{"issue":"1","key":"9352_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02897056","volume":"104","author":"P. Valtr","year":"1998","unstructured":"Valtr, P.: Guarding galleries where no point sees a small area. Isr. J. Math. 104(1), 1\u201316 (1998)","journal-title":"Isr. J. Math."},{"issue":"2","key":"9352_CR22","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V.N. Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-011-9352-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-011-9352-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-011-9352-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:50:34Z","timestamp":1559087434000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-011-9352-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9352"],"URL":"https:\/\/doi.org\/10.1007\/s00454-011-9352-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,6]]}}}