{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:20:40Z","timestamp":1760440840069},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642036842"},{"type":"electronic","value":"9783642036859"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_11","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T02:39:51Z","timestamp":1250822391000},"page":"140-148","source":"Crossref","is-referenced-by-count":7,"title":["An Approximation Scheme for Terrain Guarding"],"prefix":"10.1007","author":[{"given":"Matt","family":"Gibson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gaurav","family":"Kanade","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Krohn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kasturi","family":"Varadarajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","unstructured":"Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B.: A constant-factor approximation algorithm for optimal terrain guarding. In: SODA, pp. 515\u2013524 (2005)"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Chan, T., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: Symposium on Computational Geometry (to appear, 2009)","DOI":"10.1145\/1542362.1542420"},{"key":"11_CR3","unstructured":"Chen, D.Z., Estivill-Castro, V., Urrutia, J.: Optimal guarding of polygons and monotone chains (extended abstract) (1996)"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1145\/1064092.1064115","volume-title":"SCG 2005: Proceedings of the twenty-first annual symposium on Computational geometry","author":"K.L. Clarkson","year":"2005","unstructured":"Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. In: SCG 2005: Proceedings of the twenty-first annual symposium on Computational geometry, pp. 135\u2013141. ACM Press, New York (2005)"},{"key":"11_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-540-73951-7_15","volume-title":"Algorithms and Data Structures","author":"A. Deshpande","year":"2007","unstructured":"Deshpande, A., Kim, T., Demaine, E.D., Sarma, S.E.: A pseudopolynomial time o(log2 n)-approximation algorithm for art gallery problems. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 163\u2013174. Springer, Heidelberg (2007)"},{"issue":"6","key":"11_CR6","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. Information Processing Letters\u00a0100(6), 238\u2013245 (2006)","journal-title":"Information Processing Letters"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/3-540-49381-6_45","volume-title":"Inapproximability results for guarding polygons without holes","author":"S. Eidenbenz","year":"1998","unstructured":"Eidenbenz, S.: Inapproximability results for guarding polygons without holes. LNCS, pp. 427\u2013436. Springer, Heidelberg (1998)"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Elbassioni, K., Krohn, E., Matijevic, D., Mestre, J., Severdija, D.: Improved approximations for guarding 1.5-dimensional terrains. In: Albers, S., Marion, J.-Y. (eds.) 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), Dagstuhl, Germany, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2009)","DOI":"10.1007\/s00453-009-9358-4"},{"issue":"6","key":"11_CR9","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T. Erlebach","year":"2005","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing\u00a034(6), 1302\u20131323 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"11_CR10","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput.\u00a016(6), 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"key":"11_CR11","unstructured":"Ghosh, S.: Approximation algorithms for art gallery problems. In: Proc. Canadian Information Processing Society Congress (1987)"},{"key":"11_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/11682462_58","volume-title":"LATIN 2006: Theoretical Informatics","author":"J. King","year":"2006","unstructured":"King, J.: A 4-approximation algorithm for guarding 1.5-dimensional terrains. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 629\u2013640. Springer, Heidelberg (2006)"},{"key":"11_CR13","unstructured":"Krohn, E., King, J.: The complexity of guarding terrains (manuscript, 2009)"},{"issue":"2","key":"11_CR14","doi-asserted-by":"publisher","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 Transactions on Information Theory\u00a032(2), 276\u2013282 (1986)","journal-title":"IEEE Transactions on Information Theory"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Mustafa, N.H., Ray, S.: Ptas for geometric hitting set problems via local search. In: Symposium on Computational Geometry (to Appear, 2009)","DOI":"10.1145\/1542362.1542367"},{"key":"11_CR16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"1362","DOI":"10.1007\/11523468_110","volume-title":"Automata, Languages and Programming","author":"B.J. Nilsson","year":"2005","unstructured":"Nilsson, B.J.: Approximate guarding of monotone and rectilinear polygons. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1362\u20131373. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T03:33:57Z","timestamp":1558496037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}