{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:24:35Z","timestamp":1760441075918},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,6,6]],"date-time":"2012-06-06T00:00:00Z","timestamp":1338940800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,7]]},"DOI":"10.1007\/s00453-012-9653-3","type":"journal-article","created":{"date-parts":[[2012,6,5]],"date-time":"2012-06-05T19:49:40Z","timestamp":1338925780000},"page":"564-594","source":"Crossref","is-referenced-by-count":19,"title":["Approximate Guarding of Monotone and Rectilinear Polygons"],"prefix":"10.1007","volume":"66","author":[{"given":"Erik A.","family":"Krohn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bengt J.","family":"Nilsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,6,6]]},"reference":[{"key":"9653_CR1","unstructured":"Aggarwal, A.: The art gallery theorem: its variations, applications and algorithmic aspects. Ph.D. thesis, Johns Hopkins University (1984)"},{"key":"9653_CR2","first-page":"45","volume-title":"Proc. 13th Canadian Conference on Computational Geometry, CCCG\u201901","author":"B. Brod\u00e9n","year":"2001","unstructured":"Brod\u00e9n, B., Hammar, M., Nilsson, B.J.: Guarding lines and 2-link polygons is APX-hard. In: Proc. 13th Canadian Conference on Computational Geometry, CCCG\u201901, pp. 45\u201348 (2001)"},{"key":"9653_CR3","volume-title":"Artis Magn\u00e6, Sive de Regulis Algebraicis Liber Unus","author":"G. Cardano","year":"1545","unstructured":"Cardano, G.: Artis Magn\u00e6, Sive de Regulis Algebraicis Liber Unus (1545). (English translation reprinted by Dover Publications in 1993 as Ars Magna or The Rules of Algebra)"},{"key":"9653_CR4","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1109\/FSCS.1990.89541","volume-title":"Proc. 31st Symposium on Foundations of Computer Science","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. In: Proc. 31st Symposium on Foundations of Computer Science, pp. 220\u2013230 (1990)"},{"key":"9653_CR5","first-page":"133","volume-title":"Proc. 7th Canadian Conference on Computational Geometry, CCCG\u201995","author":"D.Z. Chen","year":"1995","unstructured":"Chen, D.Z., Estivill-Castro, V., Urrutia, J.: Optimal guarding of polygons and monotone chains. In: Proc. 7th Canadian Conference on Computational Geometry, CCCG\u201995, pp. 133\u2013138 (1995)"},{"key":"9653_CR6","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0020-0190(88)90141-X","volume":"28","author":"W. Chin","year":"1988","unstructured":"Chin, W., Ntafos, S.: Optimum Watchman routes. Inf. Process. Lett. 28, 39\u201344 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"9653_CR7","first-page":"395","volume":"13","author":"V. Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: A combinatorial theorem in plane geometry. J. Comb. Theory, B 13(6), 395\u2013398 (1975)","journal-title":"J. Comb. Theory, B"},{"key":"9653_CR8","volume-title":"Proc. 21st ACM Symposium on Computational Geometry","author":"K.L. Clarkson","year":"2005","unstructured":"Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. In: Proc. 21st ACM Symposium on Computational Geometry (2005)"},{"key":"9653_CR9","first-page":"601","volume-title":"Proc. 29th Symposium on Foundations of Computer Science","author":"J.C. Culberson","year":"1988","unstructured":"Culberson, J.C., Reckhow, R.A.: Covering polygons is hard. In: Proc. 29th Symposium on Foundations of Computer Science, pp. 601\u2013611 (1988)"},{"issue":"1","key":"9653_CR10","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0925-7721(91)90010-C","volume":"1","author":"M. Berg de","year":"1991","unstructured":"de Berg, M.: On rectilinear link distance. Comput. Geom., Theory Appl. 1(1), 13\u201334 (1991)","journal-title":"Comput. Geom., Theory Appl."},{"key":"9653_CR11","series-title":"Lecture Notes in Computer Science","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, WADS\u201907","author":"A. Deshpande","year":"2007","unstructured":"Deshpande, A., Kim, T., Demaine, E.D., Sarna, S.E.: A pseudopolynomial time O(logn)-approximation algorithm for art gallery problems. In: Proc. 10th Workshop on Algorithms and Data Structures, WADS\u201907. Lecture Notes in Computer Science, vol. 4619, pp. 163\u2013174. Springer, Berlin (2007)"},{"key":"9653_CR12","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, 238\u2013245 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9653_CR13","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/3-540-49381-6_45","volume-title":"Proc. 9th Annual International Symposium on Algorithms and Computation","author":"S. Eidenbenz","year":"1998","unstructured":"Eidenbenz, S.: Inapproximability results for guarding polygons without holes. In: Proc. 9th Annual International Symposium on Algorithms and Computation, pp. 427\u2013436 (1998)"},{"key":"9653_CR14","unstructured":"Eidenbenz, S.: Inapproximability of visibility problems on polygons and terrains. Ph.D. thesis, ETH, Zurich (2000)"},{"key":"9653_CR15","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/0196-6774(81)90019-5","volume":"2","author":"H. ElGindy","year":"1981","unstructured":"ElGindy, H., Avis, D.: A linear algorithm for computing the visibility polygon from a point. J. Algorithms 2, 186\u2013197 (1981)","journal-title":"J. Algorithms"},{"key":"9653_CR16","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/BF01895856","volume":"29","author":"L. Fejes T\u00f3th","year":"1977","unstructured":"Fejes T\u00f3th, L.: Illumination of convex discs. Acta Math. Acad. Sci. Hung. 29, 355\u2013360 (1977)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"9653_CR17","doi-asserted-by":"crossref","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 Chv\u00e1tal\u2019s Watchman theorem. J. Comb. Theory, B 24, 374 (1978)","journal-title":"J. Comb. Theory, B"},{"key":"9653_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9653_CR19","volume-title":"Proceedings of the Canadian Information Processing Society Congress","author":"S.K. Ghosh","year":"1987","unstructured":"Ghosh, S.K.: Approximation algorithms for art gallery problems. In: Proceedings of the Canadian Information Processing Society Congress (1987)"},{"key":"9653_CR20","volume-title":"Handbook of Discrete and Computational Geometry","year":"1997","unstructured":"Goodman, J.E., O\u2019Rourke, J. (eds.): Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton (1997)"},{"key":"9653_CR21","first-page":"39","volume-title":"Proc. 32nd IEEE Symposium on the Foundations of Computer Science","author":"F. Hoffmann","year":"1991","unstructured":"Hoffmann, F., Kaufmann, M., Kriegel, K.: The art gallery theorem for polygons with holes. In: Proc. 32nd IEEE Symposium on the Foundations of Computer Science, pp. 39\u201348 (1991)"},{"key":"9653_CR22","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1007\/BF01937271","volume":"27","author":"B. Joe","year":"1987","unstructured":"Joe, B., Simpson, R.B.: Correction to Lee\u2019s visibility polygon algorithm. BIT 27, 458\u2013473 (1987)","journal-title":"BIT"},{"key":"9653_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1007\/11785293_22","volume-title":"Proc. 10th Scandinavian Workshop on Algorithm Theory","author":"M.J. Katz","year":"2006","unstructured":"Katz, M.J., Roisman, G.S.: On guarding rectilinear domains. In: Proc. 10th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 4059, pp. 220\u2013231. Springer, Berlin (2006)"},{"key":"9653_CR24","doi-asserted-by":"crossref","first-page":"1580","DOI":"10.1137\/1.9781611973075.128","volume-title":"Proc. 21st ACM-SIAM Symposium on Discrete Algorithms, SODA\u201910","author":"J. King","year":"2010","unstructured":"King, J., Krohn, E.: Terrain guarding is NP-hard. In: Proc. 21st ACM-SIAM Symposium on Discrete Algorithms, SODA\u201910, pp. 1580\u20131593 (2010)"},{"key":"9653_CR25","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0734-189X(83)90065-8","volume":"22","author":"D.T. Lee","year":"1983","unstructured":"Lee, D.T.: Visibility of a simple polygon. Comput. Vis. Graph. Image Process. 22, 207\u2013221 (1983)","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"9653_CR26","doi-asserted-by":"crossref","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. Inf. Theory IT-32, 276\u2013282 (1986)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9653_CR27","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1145\/322139.322142","volume":"26","author":"D.T. Lee","year":"1979","unstructured":"Lee, D.T., Preparata, F.P.: An optimal algorithm for finding the kernel of a polygon. J. ACM 26, 415\u2013421 (1979)","journal-title":"J. ACM"},{"key":"9653_CR28","unstructured":"Levcopoulos, C.: Heuristics for minimum decompositions of polygons. Ph.D. thesis, University of Link\u00f6ping, Link\u00f6ping, Sweden (1987)"},{"key":"9653_CR29","series-title":"Lecture Notes in Computer Science","first-page":"63","volume-title":"Proc. 1st Symposium on the Theoretical Aspects of Computer Science","author":"C. Levcopoulos","year":"1984","unstructured":"Levcopoulos, C., Lingas, A.: Covering polygons with minimum number of rectangles. In: Proc. 1st Symposium on the Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 166, pp. 63\u201372. Springer, Berlin (1984)"},{"key":"9653_CR30","unstructured":"Nilsson, B.J.: Guarding art galleries\u2014methods for mobile guards. Ph.D. thesis, Lund University (1995)"},{"key":"9653_CR31","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)"},{"key":"9653_CR32","volume-title":"Handbook on Computational Geometry","year":"1999","unstructured":"Sack, J.R., Urrutia, J. (eds.): Handbook on Computational Geometry. Elsevier, Amsterdam (1999)"},{"key":"9653_CR33","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1109\/5.163407","volume":"September","author":"T.C. Shermer","year":"1992","unstructured":"Shermer, T.C.: Recent results in art galleries. Proc. IEEE September, 1384\u20131399 (1992)","journal-title":"Proc. IEEE"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9653-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9653-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9653-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:09Z","timestamp":1559137509000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9653-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,6]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["9653"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9653-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6,6]]}}}