Abstract
We provide an O(log log opt)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building ε-nets of size \(O(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon})\) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Brönnimann and Goodrich to build an approximation algorithm from this ε-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon’s vertices. If a finite set of potential guard locations is not specified, e.g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm’s running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log opt)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aggarwal, A.: The art gallery theorem: its variations, applications and algorithmic aspects. Ph.D. thesis, The Johns Hopkins University, Baltimore, MD (1984)
Aronov, B., Ezra, E., Sharir, M.: Small-size ε-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248–3282 (2010)
Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4), 929–965 (1989)
Bose, P., Lubiw, A., Munro, J.I.: Efficient visibility queries in simple polygons. Comput. Geom. Theory Appl. 23(3), 313–335 (2002)
Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(1), 463–479 (1995)
Chvátal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233–235 (1979)
Deshpande, A., Kim, T., Demaine, E.D., Sarma, S.E.: A pseudopolynomial time O(log n)-approximation algorithm for art gallery problems. In: Proc. 10th Workshop on Algorithms and Data Structures, Halifax, Canada, pp. 163–174 (2007)
Efrat, A., Har-Peled, S.: Guarding galleries and terrains. Inf. Process. Lett. 100(6), 238–245 (2006)
Eidenbenz, S.: Inapproximability results for guarding polygons without holes. In: Proc. 9th Int. Symp. Algorithms and Computation. Lecture Notes in Computer Science, vol. 1533, pp. 427–436 (1998)
Eidenbenz, S., Stamm, C., Widmayer, P.: Inapproximability results for guarding polygons and terrains. Algorithmica 31(1), 79–113 (2001)
Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634–652 (1998)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Ghosh, S.: Approximation algorithms for art gallery problems. In: Proc. Canadian Information Processing Society Congress, pp. 429–436 (1987)
Kalai, G., Matoušek, J.: Guarding galleries where every point sees a large area. Isr. J. Math. 101(1), 125–139 (1997)
King, J.: VC-dimension of visibility on terrains. In: Proc. 20th Canadian Conference on Computational Geometry, Montreal, Canada, pp. 27–30 (2008)
Komlós, J., Pach, J., Woeginger, G.: Almost tight bounds for ε-nets. Discrete Comput. Geom. 7(1), 163–173 (1992)
Lee, D., Lin, A.: Computational complexity of art gallery problems. IEEE Trans. Inf. Theory 32, 276–282 (1986)
O’Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, London (1987)
O’Rourke, J., Supowit, K.J.: Some NP-hard polygon decomposition problems. IEEE Trans. Inf. Theory 29(2), 181–189 (1983)
Raz, R., Safra, S.: A sub-constant error-probability low-degree-test and a sub-constant error-probability PCP characterization of NP. In: Proc. 29th ACM Symp. Theory of Computing. El Paso, TX, pp. 475–484 (1997)
Valtr, P.: Guarding galleries where no point sees a small area. Isr. J. Math. 104(1), 1–16 (1998)
Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264–280 (1971)
Author information
Authors and Affiliations
Corresponding author
Additional information
Some of these results appeared in preliminary form as D. Kirkpatrick. Guarding galleries with no nooks. In Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG’00), pp. 43–46, 2000.
Rights and permissions
About this article
Cite this article
King, J., Kirkpatrick, D. Improved Approximation for Guarding Simple Galleries from the Perimeter. Discrete Comput Geom 46, 252–269 (2011). https://doi.org/10.1007/s00454-011-9352-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-011-9352-x