{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:17:58Z","timestamp":1760440678268},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540739487"},{"type":"electronic","value":"9783540739517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73951-7_15","type":"book-chapter","created":{"date-parts":[[2007,8,20]],"date-time":"2007-08-20T10:18:03Z","timestamp":1187605083000},"page":"163-174","source":"Crossref","is-referenced-by-count":12,"title":["A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems"],"prefix":"10.1007","author":[{"given":"Ajay","family":"Deshpande","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taejung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjay E.","family":"Sarma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","unstructured":"Bose, P., Lubiw, A., Munro, J.I.: Efficient visibility queries in simple polygons. In: Proc. 4th Canad. Conf. Comput. Geom., pp. 23\u201328 (1992)"},{"issue":"4","key":"15_CR2","doi-asserted-by":"publisher","first-page":"1120","DOI":"10.1137\/S0097539792233257","volume":"26","author":"L.J. Guibas","year":"1997","unstructured":"Guibas, L.J., Motwani, R., Raghavan, P.: The robot localization problem. SIAM J. Comput.\u00a026(4), 1120\u20131138 (1997)","journal-title":"SIAM J. Comput."},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Gonz\u00e1lez-Banos, H., Latombe, J.: A randomized art-gallery algorithm for sensor placement. In: Proc. 17th Symp. Comput. Goem, pp. 232\u2013240 (2001)","DOI":"10.1145\/378583.378674"},{"key":"15_CR4","doi-asserted-by":"publisher","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\u00a031, 79\u2013113 (2001)","journal-title":"Algorithmica"},{"key":"15_CR5","unstructured":"Ghosh, S.: Approximation algorithm for art gallery problems. In: Canad. Information Processing Soc. Congress (1987)"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. In: Proc. 10th Symp. Comp. Geom., pp. 293\u2013302 (1994)","DOI":"10.1145\/177424.178029"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Urrutia, J.: Art Gallery and Illumination Problems. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry (2000)","DOI":"10.1016\/B978-044482537-7\/50023-1"},{"key":"15_CR8","unstructured":"O\u2019Rourke, J.: Art Gallery Theorems and Algorithms (1987)"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1109\/5.163407","volume":"80","author":"T. Shermer","year":"1992","unstructured":"Shermer, T.: Recent results in art galleries. Proc. IEEE\u00a080, 1384\u20131399 (1992)","journal-title":"Proc. IEEE"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V. Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: A combinatorial theorem in plane geometry. J. Combinat. Theory B\u00a018, 39\u201341 (1975)","journal-title":"J. Combinat. Theory B"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TIT.1986.1057165","volume":"IT-32","author":"D.T. Lee","year":"1986","unstructured":"Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Info. Theory\u00a0IT-32, 276\u2013282 (1986)","journal-title":"IEEE Trans. Info. Theory"},{"key":"15_CR12","unstructured":"Brod\u00e9n, B., Hammar, M., Nilsson, B.J.: Guarding lines and 2-link polygons is APX-hard. In: Proc. 13th Canad. Conf. Comp. Geom., pp. 45\u201348 (2001)"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Erickson, J.: Nice point sets can have nasty Delaunay triangulations. In: Proc. 17th Symp. Comp. Geom., pp. 96\u2013105 (2001)","DOI":"10.1145\/378583.378636"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Erickson, J.: Dense point sets have sparse Delaunay triangulations: or \u201c...but not too nasty\u201d. In: Proc. 13th Symp. Disc. Algo., pp. 125\u2013134 (2002)","DOI":"10.1145\/378583.378636"},{"issue":"6","key":"15_CR15","doi-asserted-by":"publisher","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. Info. Proc. Lett.\u00a0100(6), 238\u2013245 (2006)","journal-title":"Info. Proc. Lett."},{"key":"15_CR16","doi-asserted-by":"publisher","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. Israel J. Math.\u00a0104, 1\u201316 (1998)","journal-title":"Israel J. Math."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73951-7_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T21:07:57Z","timestamp":1684012077000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73951-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540739487","9783540739517"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73951-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}