{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T22:54:33Z","timestamp":1790117673552,"version":"4.0.1"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2007,1]]},"abstract":"We present the first constant\u2010factor approximation algorithm for a nontrivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an $O(1)$\u2010approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic\u2010factor approximations follow from set cover results, our new results exploit the geometric structure of terrains to obtain a substantially improved approximation algorithm.<\/jats:p>","DOI":"10.1137\/s0097539704446384","type":"journal-article","created":{"date-parts":[[2007,2,26]],"date-time":"2007-02-26T17:51:01Z","timestamp":1172512261000},"page":"1631-1647","source":"Crossref","is-referenced-by-count":35,"title":["A Constant\u2010Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding"],"prefix":"10.1137","volume":"36","author":[{"given":"Boaz","family":"Ben\u2010Moshe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,2,26]]},"reference":[{"key":"R1","unstructured":"B. Ben\u2010Moshe, M. J. Katz, and J. S. B. Mitchell,\n A constant\u2010factor approximation algorithm for optimal terrain guarding\n , in Proceedings of the 16th Annual ACM\u2010SIAM Symposium Discrete Algorithms, Vancouver, BC, 2005, SIAM, Philadelphia, 2005, pp. 515\u2013524."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00034-8"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"R4","unstructured":"D. Z. Chen, V. Estivill\u2010Castro, and J. Urrutia,\n Optimal guarding of polygons and monotone chains\n , in Proceedings of the 7th Annual Canadian Conference on Computational Geometry, Quebec City, QB, 1995, pp. 133\u2013138."},{"key":"R5","unstructured":"O. Cheong, A. Efrat, and S. Har\u2010Peled,\n On finding a guard that sees most and a shop that sells most\n , in Proceedings of the 15th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, SIAM, Philadelphia, 2004, pp. 1091\u20131100."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. Efrat and S. Har\u2010Peled,\n Locating guards in art galleries\n , in Proceedings of the 2nd Annual IFIP International Conference on Theoretical Computer Science, Montr\u00e9al, QB, 2002, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002, pp. 181\u2013192.","DOI":"10.1007\/978-0-387-35608-2_16"},{"key":"R7","unstructured":"S. J. Eidenbenz,\n (In\u2010)Approximability of Visibility Problems on Polygons and Terrains\n , Ph.D. thesis, Department of Computer Science, ETH Z\u00fcrich, Switzerland, 2000."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00255-1"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0040-8"},{"key":"R10","unstructured":"S. K. Ghosh,\n Approximation algorithms for art gallery problems\n , in Proceedings of the Canadian Information Processing Society Congress, 1987, pp. 429\u2013434."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"H. Gonz\u00e1lez\u2010Banos and J.\u2010C. Latombe,\n A randomized art\u2010gallery algorithm for sensor placement\n , in Proceedings of the 17th Annual ACM Symposium on Computational Geometry, Medford, MA, 2001, pp. 232\u2013240.","DOI":"10.1145\/378583.378674"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. M. Keil,\n Polygon decomposition\n , in Handbook of Computational Geometry, J.\u2010R. Sack and J. Urrutia, eds., Elsevier Science, North\u2013Holland, Amsterdam, 2000, pp. 491\u2013518.","DOI":"10.1016\/B978-044482537-7\/50012-7"},{"key":"R13","unstructured":"B. J. Nilsson,\n Guarding Art Galleries\u2014Methods for Mobile Guards\n , Ph.D. thesis, Department of Computer Science, Lund University, Lund, Sweden, 1995."},{"key":"R14","unstructured":"J. O\u2019Rourke,\n Art Gallery Theorems and Algorithms\n , Internat. Ser. Monogr. Comput. Sci., Oxford University Press, New York, 1987."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056648"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/5.163407"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"J. Urrutia,\n Art gallery and illumination problems\n , in Handbook of Computational Geometry, J.\u2010R. Sack and J. Urrutia, eds., North\u2013Holland, Amsterdam, 2000, pp. 973\u20131027.","DOI":"10.1016\/B978-044482537-7\/50023-1"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539704446384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:26:21Z","timestamp":1787336781000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539704446384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":17,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/S0097539704446384"],"URL":"https:\/\/doi.org\/10.1137\/s0097539704446384","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}