On guarding the vertices of rectilinear domains. (English) Zbl 1149.65015
Two problems on visibility coverage are studied. One is the problem of guarding the vertices of a rectilinear polygon \(P\), which is considered in three different versions which are proved to be NP-hard. The three cases are the following: 1) guards may lie anywhere on the boundary of \(P\), 2) guards may lie only at vertices of \(P\), 3) guards may lie anywhere in \(P\).
A 1.5D rectilinear terrain, which is defined by an \(x\)-monotone chain \(T\) of horizontal and vertical line segments, is the region to be guarded in the second problem considered in the article. A connection is established between this problem and the problem of computing a minimum clique cover in chordal graphs. A \(2\)-approximation algorithm for the guarding problem is described.
Each part of the article is summarized in terms of a theorem.
A 1.5D rectilinear terrain, which is defined by an \(x\)-monotone chain \(T\) of horizontal and vertical line segments, is the region to be guarded in the second problem considered in the article. A connection is established between this problem and the problem of computing a minimum clique cover in chordal graphs. A \(2\)-approximation algorithm for the guarding problem is described.
Each part of the article is summarized in terms of a theorem.
Reviewer: Jesus Illán González (Vigo)
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 68W05 | Nonnumerical algorithms |
Keywords:
geometric optimization; guarding; NP-hardness; approximation algorithms; visibility coverage; piercing problemsReferences:
| [1] | A. Aggarwal, The art gallery theorem: Its variations, applications and algorithmic aspects, PhD thesis, Johns Hopkins University, 1984; A. Aggarwal, The art gallery theorem: Its variations, applications and algorithmic aspects, PhD thesis, Johns Hopkins University, 1984 |
| [2] | B. Ben-Moshe, M.J. Katz, J.S.B. Mitchell, A constant-factor approximation algorithm for optimal terrain guarding, in: Proc. 16th ACM-SIAM Sympos. on Discrete Algorithms, 2005, pp. 515-524; B. Ben-Moshe, M.J. Katz, J.S.B. Mitchell, A constant-factor approximation algorithm for optimal terrain guarding, in: Proc. 16th ACM-SIAM Sympos. on Discrete Algorithms, 2005, pp. 515-524 · Zbl 1297.68260 |
| [3] | Bose, P.; Shermer, T.; Toussaint, G.; Zhu, B., Guarding polyhedral terrains, Comput. Geom. Theory Appl., 7, 173-185 (1997) · Zbl 0869.68113 |
| [4] | B. Brodén, M. Hammar, B.J. Nilsson, Guarding lines and 2-link polygons is APX-hard, in: Proc. 13th Canad. Conf. Comput. Geom., 2001, pp. 45-48; B. Brodén, M. Hammar, B.J. Nilsson, Guarding lines and 2-link polygons is APX-hard, in: Proc. 13th Canad. Conf. Comput. Geom., 2001, pp. 45-48 |
| [5] | Brönnimann, H.; Goodrich, M. T., Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom., 14, 263-279 (1995) · Zbl 0841.68122 |
| [6] | D.Z. Chen, V. Estivill-Castro, J. Urrutia, Optimal guarding of polygons and monotone chains, in: Proc. 7th Canad. Conf. Comput. Geom., 1995, pp. 133-138; D.Z. Chen, V. Estivill-Castro, J. Urrutia, Optimal guarding of polygons and monotone chains, in: Proc. 7th Canad. Conf. Comput. Geom., 1995, pp. 133-138 |
| [7] | Chvátal, V., A combinatorial theorem in plane geometry, Combinatorial Theory Series B, 18, 39-41 (1975) · Zbl 0278.05028 |
| [8] | K.L. Clarkson, K.R. Varadarajan, Improved approximation algorithms for geometric set cover, in: Proc. 21st Annu. ACM Sympos. Comput. Geom., 2005, pp. 135-141; K.L. Clarkson, K.R. Varadarajan, Improved approximation algorithms for geometric set cover, in: Proc. 21st Annu. ACM Sympos. Comput. Geom., 2005, pp. 135-141 · Zbl 1379.68347 |
| [9] | Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76 (1961) · Zbl 0098.14703 |
| [10] | A. Efrat, S. Har-Peled, Locating guards in art galleries, in: 2nd IFIP International Conference on Theoretical Computer Science, 2002, pp. 181-192; A. Efrat, S. Har-Peled, Locating guards in art galleries, in: 2nd IFIP International Conference on Theoretical Computer Science, 2002, pp. 181-192 |
| [11] | S.J. Eidenbenz, (In-)approximability of visibility problems on polygons and terrains, PhD thesis, ETH Zürich, Switzerland, 2000; S.J. Eidenbenz, (In-)approximability of visibility problems on polygons and terrains, PhD thesis, ETH Zürich, Switzerland, 2000 |
| [12] | Eidenbenz, S. J.; Stamm, C.; Widmayer, P., Inapproximability results for guarding polygons and terrains, Algorithmica, 31, 79-113 (2001) · Zbl 0980.68140 |
| [13] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039 |
| [14] | Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Computing, 1, 2, 180-187 (1972) · Zbl 0227.05116 |
| [15] | S.K. Ghosh, Approximation algorithms for art gallery problems, in: Proc. Canadian Inform. Process. Soc. Congress, 1987, pp. 429-434; S.K. Ghosh, Approximation algorithms for art gallery problems, in: Proc. Canadian Inform. Process. Soc. Congress, 1987, pp. 429-434 |
| [16] | H. González-Banos, J.-C. Latombe, A randomized art-gallery algorithm for sensor placement, in: Proc. 17th Annual Symposium on Computational Geometry, 2001, pp. 232-240; H. González-Banos, J.-C. Latombe, A randomized art-gallery algorithm for sensor placement, in: Proc. 17th Annual Symposium on Computational Geometry, 2001, pp. 232-240 · Zbl 1375.68139 |
| [17] | Hershberger, J., An optimal visibility graph algorithm for triangulated simple polygons, Algorithmica, 4, 141-155 (1989) · Zbl 0662.68041 |
| [18] | Keil, J. M., Polygon decomposition, (Sack, J.-R.; Urrutia, J., Handbook of Computational Geometry (2000), Elsevier Science Publishers B.V./North-Holland: Elsevier Science Publishers B.V./North-Holland Amsterdam), 491-518 · Zbl 0948.68189 |
| [19] | King, J., A 4-approximation algorithm for guarding 1.5-dimensional terrains, (Proc. LATIN. Proc. LATIN, Lecture Notes Comput. Sci., vol. 3887 (2006), Springer: Springer Berlin), 629-640 · Zbl 1145.68596 |
| [20] | V.S.A. Kumar, S. Arya, H. Ramesh, Hardness of a set cover with intersection 1, in: Proc. 27th International Colloquium, ICALP, 2000, pp. 624-635; V.S.A. Kumar, S. Arya, H. Ramesh, Hardness of a set cover with intersection 1, in: Proc. 27th International Colloquium, ICALP, 2000, pp. 624-635 · Zbl 0973.68080 |
| [21] | Lee, D. T.; Lin, A. K., Computational complexity of art gallery problems, IEEE Trans. Inform. Theory, IT-32, 276-282 (1986) · Zbl 0593.68035 |
| [22] | Megiddo, N.; Tamir, A., On the complexity of locating linear facilities in the plane, Oper. Res. Lett., 1, 194-197 (1982) · Zbl 0507.90025 |
| [23] | Motwani, R.; Raghunathan, A.; Saran, H., Covering orthogonal polygons with star polygons: The perfect graph approach, Comput. Syst. Sci., 40, 19-48 (1990) · Zbl 0705.68082 |
| [24] | B.J. Nilsson, Approximate guarding of monotone and rectilinear polygons, in: Proc. 32nd International Colloquium, ICALP, 2005, pp. 1362-1373; B.J. Nilsson, Approximate guarding of monotone and rectilinear polygons, in: Proc. 32nd International Colloquium, ICALP, 2005, pp. 1362-1373 · Zbl 1081.68729 |
| [25] | O’Rourke, J., Art Gallery Theorems and Algorithms, The International Series of Monographs on Computer Science (1987), Oxford University Press: Oxford University Press New York · Zbl 0653.52001 |
| [26] | O’Rourke, J.; Supowit, K. J., Some NP-hard polygon decomposition problems, IEEE Trans. Inform. Theory, IT-30, 181-190 (1983) · Zbl 0501.68036 |
| [27] | Shermer, T. C., Recent results in art galleries, Proc. IEEE, 80, 9, 1384-1399 (1992) |
| [28] | Schuchardt, D.; Hecker, H.-D., Two NP-hard art-gallery problems for ortho-polygons, Mathematical Logic Quarterly, 41, 261-267 (1995) · Zbl 0827.68115 |
| [29] | Urrutia, J., Art gallery and illumination problems, (Sack, J.-R.; Urrutia, J., Handbook of Computational Geometry (2000), Elsevier Science Publishers B.V./North-Holland: Elsevier Science Publishers B.V./North-Holland Amsterdam), 973-1027 · Zbl 0941.68138 |
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.
