Document Open Access Logo

An Approximation Algorithm for the Art Gallery Problem

Authors Édouard Bonnet, Tillmann Miltzow

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.20.pdf
  • Filesize: 0.88 MB
  • 15 pages

Document Identifiers

Author Details

Édouard Bonnet
Tillmann Miltzow

Cite AsGet BibTex

Édouard Bonnet and Tillmann Miltzow. An Approximation Algorithm for the Art Gallery Problem. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.20

Abstract

Given a simple polygon P on n vertices, two points x, y in P are said to be visible to each other if the line segment between x and y is contained in P. The Point Guard Art Gallery problem asks for a minimum-size set S such that every point in P is visible from a point in S. The set S is referred to as guards. Assuming integer coordinates and a specific general position on the vertices of P, we present the first O(log OPT)-approximation algorithm for the point guard problem. This algorithm combines ideas in papers of Efrat and Har-Peled and Deshpande et al. We also point out a mistake in the latter.
Keywords
  • computational geometry
  • art gallery
  • approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Eyüp Serdar Ayaz and Alper Üngör. Minimal witness sets for art gallery problems. EuroCG, 2016. Google Scholar
  2. János Barát, Vida Dujmovic, Gwenaël Joret, Michael S. Payne, Ludmila Scharf, Daria Schymura, Pavel Valtr, and David R. Wood. Empty pentagons in point sets with collinearities. SIAM J. Discrete Math., 29(1):198-209, 2015. Google Scholar
  3. Saugata Basu, Richard Pollack, and Marie-Francoise Roy. Algorithms in real algebraic geometry. Springer, 2007. Google Scholar
  4. Patrice Belleville. Computing two-covers of simple polygons. Master’s thesis, McGill University, 1991. Google Scholar
  5. Vijay V. S. P. Bhattiprolu and Sariel Har-Peled. Separating a voronoi diagram via local search. In SOCG, pages 18:1-18:16, 2016. Google Scholar
  6. Édouard Bonnet and Tillmann Miltzow. An approximation algorithm for the art gallery problem. CoRR, 1607.05527, 2016. URL: http://arxiv.org/abs/1607.05527.
  7. Édouard Bonnet and Tillmann Miltzow. The parameterized hardness of the art gallery problem. In ESA 2016, pages 19:1-19:17, 2016. Arxiv identifier: 1603.08116. Google Scholar
  8. Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Computational Geometry, 14(4):463-479, 1995. URL: http://dx.doi.org/10.1007/BF02570718.
  9. John Canny. Some algebraic and geometric computations in PSPACE. In STOC, pages 460-467. ACM, 1988. Google Scholar
  10. Jean Cardinal. Computational geometry column 62. SIGACT News, 46(4):69-78, December 2015. URL: http://dx.doi.org/10.1145/2852040.2852053.
  11. Václav Chvátal. A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Series B, 18(1):39-41, 1975. Google Scholar
  12. Kyung-Yong Chwa, Byung-Cheol Jo, Christian Knauer, Esther Moet, René van Oostrum, and Chan-Su Shin. Guarding art galleries by guarding witnesses. Int. J. Comput. Geometry Appl., 16(2-3):205-226, 2006. Google Scholar
  13. Kenneth L. Clarkson. Algorithms for polytope covering and approximation. In WADS 1993, pages 246-252, 1993. URL: http://dx.doi.org/10.1007/3-540-57155-8_252.
  14. Pedro Jussieu de Rezende, Cid C. de Souza, Stephan Friedrichs, Michael Hemmer, Alexander Kröller, and Davi C. Tozoni. Engineering art galleries. CoRR, abs/1410.8720, 2014. URL: http://arxiv.org/abs/1410.8720.
  15. Ajay Deshpande. A pseudo-polynomial time O(log² n)-approximation algorithm for art gallery problems. Master’s thesis, Department of Mechanical Engineering, Department of Electrical Engineering and Computer Science, MIT, 2006. Google Scholar
  16. Ajay Deshpande, Taejung Kim, Erik D. Demaine, and Sanjay E. Sarma. A pseudopolynomial time O(log n)-approximation algorithm for art gallery problems. In WADS 2007, pages 163-174, 2007. URL: http://dx.doi.org/10.1007/978-3-540-73951-7_15.
  17. Stephane Durocher and Saeed Mehrabi. Guarding orthogonal art galleries using sliding cameras: algorithmic and hardness results. In MFCS 2013, pages 314-324. Springer, 2013. Google Scholar
  18. Alon Efrat and Sariel Har-Peled. Guarding galleries and terrains. Inf. Process. Lett., 100(6):238-245, 2006. URL: http://dx.doi.org/10.1016/j.ipl.2006.05.014.
  19. Stephan Eidenbenz, Christoph Stamm, and Peter Widmayer. Inapproximability results for guarding polygons and terrains. Algorithmica, 31(1):79-113, 2001. Google Scholar
  20. Khaled Elbassioni. Finding small hitting sets in infinite range spaces of bounded VC-dimension. CoRR, abs/1610.03812, 2016. accepted to SoCG 2017. Google Scholar
  21. Steve Fisk. A short proof of Chvátal’s watchman theorem. J. Comb. Theory, Ser. B, 24(3):374, 1978. URL: http://dx.doi.org/10.1016/0095-8956(78)90059-X.
  22. Stephan Friedrichs, Michael Hemmer, James King, and Christiane Schmidt. The continuous 1.5d terrain guarding problem: Discretization, optimal solutions, and PTAS. JoCG, 7, 2016. Google Scholar
  23. Subir Kumar Ghosh. Approximation algorithms for art gallery problems in polygons. Discrete Applied Mathematics, 158(6):718-722, 2010. Google Scholar
  24. Alexander Gilbers and Rolf Klein. A new upper bound for the VC-dimension of visibility regions. Computational Geometry, 47(1):61-74, 2014. Google Scholar
  25. Heuna Kim and Günter Rote. Congruence testing of point sets in 4-space. In SoCG, volume 51 of LIPIcs, pages 48:1-48:16, 2016. Arxiv identifier: 1603.07269. Google Scholar
  26. James King. Fast vertex guarding for polygons with and without holes. Comput. Geom., 46(3):219-231, 2013. URL: http://dx.doi.org/10.1016/j.comgeo.2012.07.004.
  27. David G. Kirkpatrick. An O(log log OPT)-approximation algorithm for multi-guarding galleries. Discrete & Computational Geometry, 53(2):327-343, 2015. URL: http://dx.doi.org/10.1007/s00454-014-9656-8.
  28. Erik A. Krohn and Bengt J. Nilsson. Approximate guarding of monotone and rectilinear polygons. Algorithmica, 66(3):564-594, 2013. Google Scholar
  29. Jirí Matousek. Intersection graphs of segments and ∃ ℝ. CoRR, 1406.2636, 2014. Google Scholar
  30. Rajeev Motwani, Arvind Raghunathan, and Huzur Saran. Covering orthogonal polygons with star polygons: The perfect graph approach. J. Comput. Syst. Sci., 40(1):19-48, 1990. URL: http://dx.doi.org/10.1016/0022-0000(90)90017-F.
  31. Joseph O'rourke. Art gallery theorems and algorithms, volume 57. Oxford University Press Oxford, 1987. Google Scholar
  32. Marcus Schaefer. Complexity of Some Geometric and Topological Problems, pages 334-344. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-11805-0_32.
  33. Thomas C. Shermer. Recent results in art galleries. IEEE, 80(9):1384-1399, 1992. Google Scholar
  34. Jorge Urrutia et al. Art gallery and illumination problems. Handbook of computational geometry, 1(1):973-1027, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact