Approximate guarding of monotone and rectilinear polygons. (English) Zbl 1267.68274
Summary: We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is \(\mathrm{OPT}\) for a rectilinear polygon, our algorithm produces a guard set of size \(O(\mathrm{OPT}^2)\).
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68W25 | Approximation algorithms |
Keywords:
computational geometry; art gallery problems; monotone polygons; rectilinear polygons; approximation algorithmsReferences:
| [1] | Aggarwal, A.: The art gallery theorem: its variations, applications and algorithmic aspects. Ph.D. thesis, Johns Hopkins University (1984) · Zbl 1141.68631 |
| [2] | Brodén, B.; Hammar, M.; Nilsson, B. J., Guarding lines and 2-link polygons is APX-hard, 45-48 (2001) |
| [3] | Cardano, G.: Artis Magnæ, Sive de Regulis Algebraicis Liber Unus (1545). (English translation reprinted by Dover Publications in 1993 as Ars Magna or The Rules of Algebra) |
| [4] | Chazelle, B., Triangulating a simple polygon in linear time, 220-230 (1990) · doi:10.1109/FSCS.1990.89541 |
| [5] | Chen, D. Z.; Estivill-Castro, V.; Urrutia, J., Optimal guarding of polygons and monotone chains, 133-138 (1995) |
| [6] | Chin, W., Ntafos, S.: Optimum Watchman routes. Inf. Process. Lett. 28, 39-44 (1988) · Zbl 0652.68042 · doi:10.1016/0020-0190(88)90141-X |
| [7] | Chvátal, V.: A combinatorial theorem in plane geometry. J. Comb. Theory, B 13(6), 395-398 (1975) · Zbl 0278.05028 |
| [8] | Clarkson, K. L.; Varadarajan, K., Improved approximation algorithms for geometric set cover (2005) · Zbl 1379.68347 |
| [9] | Culberson, J. C.; Reckhow, R. A., Covering polygons is hard, 601-611 (1988) |
| [10] | de Berg, M.: On rectilinear link distance. Comput. Geom., Theory Appl. 1(1), 13-34 (1991) · Zbl 0731.68094 · doi:10.1016/0925-7721(91)90010-C |
| [11] | Deshpande, A.; Kim, T.; Demaine, E. D.; Sarna, S. E., A pseudopolynomial time O(logn)-approximation algorithm for art gallery problems, No. 4619, 163-174 (2007), Berlin · Zbl 1209.68582 · doi:10.1007/978-3-540-73951-7_15 |
| [12] | Efrat, A., Har-Peled, S.: Guarding galleries and terrains. Inf. Process. Lett. 100, 238-245 (2006) · Zbl 1185.68776 · doi:10.1016/j.ipl.2006.05.014 |
| [13] | Eidenbenz, S., Inapproximability results for guarding polygons without holes, 427-436 (1998) · doi:10.1007/3-540-49381-6_45 |
| [14] | Eidenbenz, S.: Inapproximability of visibility problems on polygons and terrains. Ph.D. thesis, ETH, Zurich (2000) |
| [15] | ElGindy, H., Avis, D.: A linear algorithm for computing the visibility polygon from a point. J. Algorithms 2, 186-197 (1981) · Zbl 0459.68057 · doi:10.1016/0196-6774(81)90019-5 |
| [16] | Fejes Tóth, L.: Illumination of convex discs. Acta Math. Acad. Sci. Hung. 29, 355-360 (1977) · Zbl 0371.52005 · doi:10.1007/BF01895856 |
| [17] | Fisk, S.: A short proof of Chvátal’s Watchman theorem. J. Comb. Theory, B 24, 374 (1978) · Zbl 0376.05018 · doi:10.1016/0095-8956(78)90059-X |
| [18] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979) · Zbl 0411.68039 |
| [19] | Ghosh, S. K., Approximation algorithms for art gallery problems (1987) |
| [20] | Goodman, J.E., O’Rourke, J. (eds.): Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton (1997) · Zbl 0890.52001 |
| [21] | Hoffmann, F.; Kaufmann, M.; Kriegel, K., The art gallery theorem for polygons with holes, 39-48 (1991) |
| [22] | Joe, B., Simpson, R.B.: Correction to Lee’s visibility polygon algorithm. BIT 27, 458-473 (1987) · Zbl 0643.68098 · doi:10.1007/BF01937271 |
| [23] | Katz, M. J.; Roisman, G. S., On guarding rectilinear domains, No. 4059, 220-231 (2006), Berlin · Zbl 1141.68631 |
| [24] | King, J.; Krohn, E., Terrain guarding is NP-hard, 1580-1593 (2010) · Zbl 1288.68095 |
| [25] | Lee, D.T.: Visibility of a simple polygon. Comput. Vis. Graph. Image Process. 22, 207-221 (1983) · Zbl 0532.68071 · doi:10.1016/0734-189X(83)90065-8 |
| [26] | Lee, D.T., Lin, A.K.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory IT-32, 276-282 (1986) · Zbl 0593.68035 · doi:10.1109/TIT.1986.1057165 |
| [27] | Lee, D.T., Preparata, F.P.: An optimal algorithm for finding the kernel of a polygon. J. ACM 26, 415-421 (1979) · Zbl 0403.68051 · doi:10.1145/322139.322142 |
| [28] | Levcopoulos, C.: Heuristics for minimum decompositions of polygons. Ph.D. thesis, University of Linköping, Linköping, Sweden (1987) |
| [29] | Levcopoulos, C.; Lingas, A., Covering polygons with minimum number of rectangles, No. 166, 63-72 (1984), Berlin · Zbl 0547.68070 |
| [30] | Nilsson, B.J.: Guarding art galleries—methods for mobile guards. Ph.D. thesis, Lund University (1995) |
| [31] | O’Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, London (1987) · Zbl 0653.52001 |
| [32] | Sack, J.R., Urrutia, J. (eds.): Handbook on Computational Geometry. Elsevier, Amsterdam (1999) · Zbl 0930.65001 |
| [33] | Shermer, T.C.: Recent results in art galleries. Proc. IEEE September, 1384-1399 (1992) · doi:10.1109/5.163407 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
