{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:36:58Z","timestamp":1743046618688,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540699002"},{"type":"electronic","value":"9783540699033"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-69903-3_6","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"41-52","source":"Crossref","is-referenced-by-count":1,"title":["Guarding Art Galleries: The Extra Cost for Sculptures Is Linear"],"prefix":"10.1007","author":[{"given":"Louigi","family":"Addario-Berry","sequence":"first","affiliation":[]},{"given":"Omid","family":"Amini","sequence":"additional","affiliation":[]},{"given":"Jean-S\u00e9bastien","family":"Sereni","sequence":"additional","affiliation":[]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"Aloupis, G., Bose, P., Dujmovi\u0107, V., Gray, C., Langerman, S., Speckmann, B.: Guarding Fat Polygons and Triangulating Guarded Polygons, September (preprint, 2007)"},{"issue":"6","key":"6_CR2","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0031-3203(81)90002-9","volume":"13","author":"D. Avis","year":"1981","unstructured":"Avis, D., Toussaint, G.T.: An efficient algorithm for decomposing a polygon into star-shaped polygons. Pattern Recognition\u00a013(6), 395\u2013398 (1981)","journal-title":"Pattern Recognition"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V. Chvatal","year":"1975","unstructured":"Chvatal, V.: A combinatorial theorem in plane geometry. J. Combin. Theory Ser. B\u00a018, 39\u201341 (1975)","journal-title":"J. Combin. Theory Ser. B"},{"key":"6_CR4","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., Taejung, K., Demaine, E.D., Sarma, S.E.: A Pseudopolynomial Time O(log copt)-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)"},{"key":"6_CR5","unstructured":"Efrat, A., Guibas, L.J., Har-Peled, S., Lin, D.C., Mitchell, J.S.B., Murali, T.M.: Sweeping simple polygons with a chain of guards. In: Proc. 11th annual ACM-SIAM symposium on Discrete algorithms, pp. 927\u2013936 (2000)"},{"issue":"2","key":"6_CR6","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0734-189X(84)80041-9","volume":"27","author":"H. Edelsbrunner","year":"1984","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Welzl, E.: Stationing guards in rectilinear art galleries. Computer vision, graphics, and image processing\u00a027(2), 167\u2013176 (1984)","journal-title":"Computer vision, graphics, and image processing"},{"issue":"1","key":"6_CR7","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(1), 79\u2013113 (2001)","journal-title":"Algorithmica"},{"issue":"3","key":"6_CR8","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/0095-8956(78)90059-X","volume":"24","author":"S. Fisk","year":"1978","unstructured":"Fisk, S.: A short proof of Chvatals watchman theorem. J. Combin. Theory Ser. B\u00a024(3), 374 (1978)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"6_CR9","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.comgeo.2006.12.001","volume":"38","author":"C. Fragoudakis","year":"2007","unstructured":"Fragoudakis, C., Markou, E., Zachos, S.: Maximizing the guarded boundary of an Art Gallery is APX-complete. Comput. Geom.\u00a038(3), 170\u2013180 (2007)","journal-title":"Comput. Geom."},{"key":"6_CR10","unstructured":"Ghosh, S.: Approximation algorithms for art gallery problems. In: Proc. Canadian Inform. Process. Soc. Congress, pp. 429\u2013434 (1987)"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Honsberger, R.: Mathematical Gems II. Dolciani Mathematical Expositions No. 2. Mathematical Association of America, Washington, pp.\u00a0104\u2013110 (1976)","DOI":"10.1090\/dol\/002"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1137\/0604020","volume":"4","author":"J. Kahn","year":"1983","unstructured":"Kahn, J., Klawe, M., Kleitman, D.: Traditional Galleries Require Fewer Watchmen. SIAM J. Algebraic Discrete Methods\u00a04, 194\u2013206 (1983)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02574368","volume":"12","author":"E. Kranakis","year":"1994","unstructured":"Kranakis, E., Pocchiola, M.: Camera placement in integer lattices. Discrete and Comput. Geom.\u00a012(1), 91\u2013104 (1994)","journal-title":"Discrete and Comput. Geom."},{"issue":"6","key":"6_CR14","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s003710050177","volume":"15","author":"A. Laurentini","year":"1999","unstructured":"Laurentini, A.: Guarding the walls of an art gallery. The Visual Computer\u00a015(6), 265\u2013278 (1999)","journal-title":"The Visual Computer"},{"key":"6_CR15","unstructured":"Liaw, B.C., Huang, N.F., Lee, R.C.T.: The minimum cooperative guards problem on k-spiral polygons. In: Proc. of 5th Canadian Conference on Computational Geometry, pp. 97\u2013101 (1993)"},{"issue":"2","key":"6_CR16","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 Trans. Inform. Theory\u00a032(2), 276\u2013282 (1986)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"3","key":"6_CR17","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/S0925-7721(03)00039-7","volume":"26","author":"T. Michael","year":"2003","unstructured":"Michael, T., Pinciu, V.: Art gallery theorems for guarded guards. Comput. Geom.\u00a026(3), 247\u2013258 (2003)","journal-title":"Comput. Geom."},{"key":"6_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, New York (1987)"},{"key":"6_CR19","unstructured":"Rote, G., Santos, F., Streinu, I.: Pseudo-triangulations: A survey, Arxiv preprint math\/0612672v1 (December 2006)"},{"key":"6_CR20","unstructured":"Sack, J.R.: An O(nlogn) algorithm for decomposing simple rectilinear polygons into convex quadrilaterals. In: Proc. 20th Conference on Communications, Control, and Computing, pp. 64\u201374 (1982)"},{"issue":"9","key":"6_CR21","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1109\/5.163407","volume":"80","author":"T.C. Shermer","year":"1992","unstructured":"Shermer, T.C.: Recent results in art galleries [geometry]. Proc. IEEE\u00a080(9), 1384\u20131399 (1992)","journal-title":"Proc. IEEE"},{"issue":"2","key":"6_CR22","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s00454-004-1091-9","volume":"33","author":"B. Speckmann","year":"2005","unstructured":"Speckmann, B., T\u00f3th, C.D.: Allocating Vertex p-Guards in Simple Polygons via Pseudo-Triangulations. Discrete Comput. Geom.\u00a033(2), 345\u2013364 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"6_CR23","first-page":"207","volume":"6","author":"L. Szabo","year":"1997","unstructured":"Szabo, L.: Recent results on illumination problems. Bolyai Soc. Math. Stud.\u00a06, 207\u2013221 (1997)","journal-title":"Bolyai Soc. Math. Stud."},{"issue":"3-4","key":"6_CR24","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/BF01895856","volume":"29","author":"L.F. T\u00f3th","year":"1977","unstructured":"T\u00f3th, L.F.: Illumination of convex discs. Acta Math. Hungar.\u00a029(3-4), 355\u2013360 (1977)","journal-title":"Acta Math. Hungar."},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Urrutia, J.: Art gallery and illumination problems. Handbook of Computational Geometry, 973\u20131027 (2000)","DOI":"10.1016\/B978-044482537-7\/50023-1"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2008"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69903-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,9]],"date-time":"2024-05-09T06:54:36Z","timestamp":1715237676000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-69903-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540699002","9783540699033"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69903-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}