Finding minimum hidden guard sets in polygons — tight approximability results. (English) Zbl 1157.65329
Summary: We study the problem Minimum Hidden Guard Set, which consists of positioning a minimum number of guards in a given polygon (or other structure such as a terrain) such that no two guards see each other and such that every point in the polygon is visible from at least one guard. By constructing a gap-creating reduction from 5-occurrence-3-satisfiability, we show that this problem cannot be approximated by any polynomial-time algorithm with an approximation ratio of \(|I|^{1-\epsilon}\) for any \(\varepsilon >0\), unless \(NP=P\), where \(|I|\) is the size of the input polygon. The result even holds for input polygons without holes, which separates the problem from other visibility problems such as guarding and hiding, where strong inapproximability results hold only for polygons with holes. We also show that a straight-forward approximation algorithm achieves an approximation ratio of \(|I|\). These two results characterize the approximability threshold of Minimum Hidden Guard Set exactly up to low-order terms.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
Keywords:
minimum Hidden guard set; inapproximability; approximation algorithm; visibility; art gallery problems; terrains; polygonsReferences:
| [1] | Arora, S.; Lund, C., Hardness of approximations, (Hochbaum, D., Approximation Algorithms for NP-Hard Problems (1996), PWS Publishing Company), 399-446 · Zbl 1368.68010 |
| [2] | Crescenzi, P.; Kann, V., A compendium of NP optimization problems, (Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties (1999), Springer: Springer Berlin), Also available in an online-version at: · Zbl 0937.68002 |
| [3] | Eidenbenz, S.; Stamm, C.; Widmayer, P., Inapproximability results for guarding polygons and terrains, Algorithmica, 31, 79-113 (2001) · Zbl 0980.68140 |
| [4] | Eidenbenz, S., Inapproximability of finding maximum hidden sets on polygons and terrains, Computational Geometry, 21, 139-153 (2002) · Zbl 0998.68190 |
| [5] | Eidenbenz, S., Approximation algorithms for terrain guarding, Inform. Process. Lett., 82, 99-105 (2002) · Zbl 1052.68130 |
| [6] | S. Ghosh, Approximation algorithms for art gallery problems, in: Proc. of the Canadian Information Processing Society Congress, 1987; S. Ghosh, Approximation algorithms for art gallery problems, in: Proc. of the Canadian Information Processing Society Congress, 1987 |
| [7] | Halldorsson, M. M., Approximating the minimum maximal independence number, Information Processing Letters, 46, 169-172 (1993) · Zbl 0778.68041 |
| [8] | Kahan, S.; Snoeyink, J., On the bit complexity of minimum link paths: Superquadratic algorithms for problems solvable in linear time, Computational Geometry, 12, 1-2, 33-44 (1999) · Zbl 0922.68121 |
| [9] | van Kreveld, M., Digital elevation models and tin algorithms, (van Kreveld, M.; etal., Algorithmic Foundations of Geographic Information Systems. Algorithmic Foundations of Geographic Information Systems, Lecture Notes in Computer Science, vol. 1340 (1997), Springer: Springer Berlin), 37-78 |
| [10] | Lee, D. T.; Lin, A. K., Computational complexity of art gallery problems, IEEE Transactions on Information Theory, IT-32, 276-282 (1986) · Zbl 0593.68035 |
| [11] | B. Nilsson, Approximate guarding of monotone and rectilinear polygons, in: Proceedings of ICALP 2005, 2005, pp. 1362-1373; B. Nilsson, Approximate guarding of monotone and rectilinear polygons, in: Proceedings of ICALP 2005, 2005, pp. 1362-1373 · Zbl 1081.68729 |
| [12] | T. Shermer, Hiding people in polygons, Computing 42, 1989, pp. 109-131; T. Shermer, Hiding people in polygons, Computing 42, 1989, pp. 109-131 · Zbl 0675.68070 |
| [13] | T. Shermer, Recent results in art galleries, in: Proc. of the IEEE, 1992; T. Shermer, Recent results in art galleries, in: Proc. of the IEEE, 1992 |
| [14] | Urrutia, J., Art gallery and illumination problems, (Sack, J. R.; Urrutia, J., Handbook on Computational Geometry (2000), North-Holland: North-Holland Amsterdam), 973-1127 · 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.
