Document Open Access Logo

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem

Authors Simon B. Hengeveld , Tillmann Miltzow

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.44.pdf
  • Filesize: 1.14 MB
  • 16 pages

Document Identifiers

Author Details

Simon B. Hengeveld
  • Université Rennes 1, France
Tillmann Miltzow
  • Utrecht University, The Netherlands

Funding

  • Hengeveld, Simon B.: MULTIBIOSTRUCT (ANR-19-CE45-0019).
  • Miltzow, Tillmann: NWO Veni grant EAGER.

Cite AsGet BibTex

Simon B. Hengeveld and Tillmann Miltzow. A Practical Algorithm with Performance Guarantees for the Art Gallery Problem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 44:1-44:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.44

Abstract

Given a closed simple polygon P, we say two points p,q see each other if the segment seg(p,q) is fully contained in P. The art gallery problem seeks a minimum size set G ⊂ P of guards that sees P completely. The only currently correct algorithm to solve the art gallery problem exactly uses algebraic methods. As the art gallery problem is ∃ ℝ-complete, it seems unlikely to avoid algebraic methods, for any exact algorithm, without additional assumptions. In this paper, we introduce the notion of vision-stability. In order to describe vision-stability consider an enhanced guard that can see "around the corner" by an angle of δ or a diminished guard whose vision is by an angle of δ "blocked" by reflex vertices. A polygon P has vision-stability δ if the optimal number of enhanced guards to guard P is the same as the optimal number of diminished guards to guard P. We will argue that most relevant polygons are vision-stable. We describe a one-shot vision-stable algorithm that computes an optimal guard set for vision-stable polygons using polynomial time and solving one integer program. It guarantees to find the optimal solution for every vision-stable polygon. We implemented an iterative vision-stable algorithm and show its practical performance is slower, but comparable with other state-of-the-art algorithms. The practical implementation can be found at: https://github.com/simonheng/AGPIterative. Our iterative algorithm is inspired and follows closely the one-shot algorithm. It delays several steps and only computes them when deemed necessary. Given a chord c of a polygon, we denote by n(c) the number of vertices visible from c. The chord-visibility width (cw(P)) of a polygon is the maximum n(c) over all possible chords c. The set of vision-stable polygons admit an FPT algorithm when parameterized by the chord-visibility width. Furthermore, the one-shot algorithm runs in FPT time when parameterized by the number of reflex vertices.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Art Gallery
  • Parametrized complexity
  • Integer Programming
  • Visibility

Metrics

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

Related Versions

Supplementary Materials

References

  1. Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl. Who needs crossings? Hardness of plane graph rigidity. In 32nd International Symposium on Computational Geometry (SoCG 2016), pages 3:1-3:15, 2016. Google Scholar
  2. Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational guards are sometimes needed. In SoCG 2017, pages 3:1-3:15, 2017. URL: http://arxiv.org/abs/1701.05475.
  3. Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ∃ ℝ-complete. In STOC 2018, pages 65-73, 2018. http://arxiv.org/abs/1704.06969, URL: https://doi.org/10.1145/3188745.3188868.
  4. Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Training neural networks is er-complete. arXiv, 2021. URL: http://arxiv.org/abs/2102.09798.
  5. Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. A framework for ∃ℝ-completeness of two-dimensional packing problems. FOCS, 2020. Google Scholar
  6. Akanksha Agrawal, Pradeesha Ashok, Meghana M. Reddy, Saket Saurabh, and Dolly Yadav. FPT algorithms for conflict-free coloring of graphs and chromatic terrain guarding. Arxiv, 1905.01822, 2019. URL: http://arxiv.org/abs/1905.01822.
  7. Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. The Parameterized Complexity of Guarding Almost Convex Polygons. In SoCG 2020, LIPIcs, pages 3:1-3:16, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.3.
  8. Akanksha Agrawal, Sudeshna Kolay, and Meirav Zehavi. Parameter analysis for guarding terrains. In SWAT, 2020. Google Scholar
  9. Akanksha Agrawal and Meirav Zehavi. Parameterized analysis of art gallery and terrain guarding. In International Computer Science Symposium in Russia, pages 16-29. Springer, 2020. Google Scholar
  10. Yoav Amit, Joseph S.B. Mitchell, and Eli Packer. Locating guards for visibility coverage of polygons. International Journal of Computational Geometry & Applications, 20(05):601-630, 2010. Google Scholar
  11. David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. TSP in practice, 2021. URL: http://www.math.uwaterloo.ca/tsp/index.html.
  12. Pradeesha Ashok and Meghana Reddy. Efficient guarding of polygons and terrains. In International Workshop on Frontiers in Algorithmics, pages 26-37. Springer, 2019. Google Scholar
  13. Patrice Belleville. Computing two-covers of simple polygons. Master’s thesis, McGill University, 1991. Google Scholar
  14. Pritam Bhattacharya, Subir Kumar Ghosh, and Sudebkumar Prasant Pal. Constant approximation algorithms for guarding simple polygons using vertex guards. arXiv, 2017. URL: http://arxiv.org/abs/1712.05492.
  15. Daniel Bienstock. Some provably hard crossing number problems. Discrete & Computational Geometry, 6(3):443-459, 1991. Google Scholar
  16. Robert Bixby. IBM CPLEX. URL: https://www.ibm.com/analytics/cplex-optimizer.
  17. Édouard Bonnet and Tillmann Miltzow. An approximation algorithm for the art gallery problem. In SoCG 2017, pages 20:1-20:15, 2017. http://arxiv.org/abs/1607.05527, URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.20.
  18. Édouard Bonnet and Tillmann Miltzow. Parameterized hardness of art gallery problems. ACM Transactions on Algorithms, 16(4), 2020. URL: https://doi.org/10.1145/3398684.
  19. Dorit Borrmann, Pedro J. de Rezende, Cid C. de Souza, Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller, Andreas Nüchter, Christiane Schmidt, and Davi C. Tozoni. Point guards and point clouds: solving general art gallery problems. In SoCG, pages 347-348. ACM, 2013. URL: https://doi.org/10.1145/2462356.2462361.
  20. Andrea Bottino and Aldo Laurentini. A nearly optimal sensor placement algorithm for boundary coverage. Pattern Recognition, 41(11):3343-3355, 2008. Google Scholar
  21. Andrea Bottino and Aldo Laurentini. A nearly optimal algorithm for covering the interior of an art gallery. Pattern Recognition, 44(5):1048-1056, 2011. Google Scholar
  22. Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber. Intersection graphs of rays and grounded segments. Journal of Graph Algorithms and Applications, 22:273-295, 2018. Google Scholar
  23. Jean Cardinal and Udo Hoffmann. Recognition and complexity of point visibility graphs. Discrete & Computational Geometry, 57(1):164-178, 2017. Google Scholar
  24. Marcelo C. Couto, Pedro J. de Rezende, and Cid C. de Souza. Instances for the Art Gallery Problem, 2009. URL: https://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery.
  25. Marcelo C. Couto, Pedro J. de Rezende, and Cid C. de Souza. An exact algorithm for minimizing vertex guards on art galleries. International Transactions in Operational Research, 18(4):425-448, 2011. Google Scholar
  26. Marcelo C. Couto, Cid C. de Souza, and Pedro J. de Rezende. Experimental evaluation of an exact algorithm for the orthogonal art gallery problem. In International Workshop on Experimental and Efficient Algorithms, pages 101-113. Springer, 2008. Google Scholar
  27. Pedro J. de Rezende, Cid C. de Souza, Stephan Friedrichs, Michael Hemmer, Alexander Kröller, and Davi C. Tozoni. Engineering art galleries. Algorithm Engineering, pages 379-417, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_12.
  28. Argyrios Deligkas, John Fearnley, and Themistoklis Melissourgos. Square-cut pizza sharing is ppa-complete. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.14236.
  29. Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Paweł Rzażewski.. ∀ ∃ ℝ-completeness and area-universality. WG 2018, 2018. URL: http://arxiv.org/abs/1712.05142.
  30. Michael Gene Dobbins, Andreas Holmsen, and Tillmann Miltzow. Smoothed analysis of the art gallery problem. arXiv, 2018. URL: http://arxiv.org/abs/1811.01177.
  31. Michael Gene Dobbins, Andreas Holmsen, and Tillmann Miltzow. A universality theorem for nested polytopes. arXiv, 2019. URL: http://arxiv.org/abs/1908.02213.
  32. Alon Efrat and Sariel Har-Peled. Guarding galleries and terrains. Inf. Process. Lett., 100(6):238-245, 2006. URL: https://doi.org/10.1016/j.ipl.2006.05.014.
  33. Stephan Eidenbenz, Christoph Stamm, and Peter Widmayer. Inapproximability results for guarding polygons and terrains. Algorithmica, 31(1):79-113, 2001. Google Scholar
  34. Jeff Erickson. Optimal curve straightening is ∃ℝ-complete. arXiv, 2019. URL: http://arxiv.org/abs/1908.09400.
  35. Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow. Smoothing the gap between NP and ∃ ℝ. accepted to FOCS 2020, 2020. URL: http://arxiv.org/abs/1912.02278.
  36. S. Friedrichs. Integer solutions for the art gallery problem using linear programming. Masterthesis, 2012. Google Scholar
  37. Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. In ICALP 2015, pages 554-566, 2015. Google Scholar
  38. Subir Kumar Ghosh. Approximation algorithms for art gallery problems in polygons. Discrete Applied Mathematics, 158(6):718-722, 2010. Google Scholar
  39. Panos Giannopoulos. Open problems: guarding problems, 2016. Google Scholar
  40. Simon Hengeveld and Tillmann Miltzow. A practical algorithm with performance guarantees for the art~ gallery problem. arXiv, 2020. URL: http://arxiv.org/abs/2007.06920.
  41. Simon Hengeveld, Tillmann Miltzow, and Frank Staals. Weak visibility by convex expansion. in preparation 2020. Google Scholar
  42. Ross J. Kang and Tobias Müller. Sphere and dot product representations of graphs. In SoCG, pages 308-314. ACM, 2011. Google Scholar
  43. Farnoosh Khodakarami, Farzad Didehvar, and Ali Mohades. A fixed-parameter algorithm for guarding 1.5 d terrains. Theoretical Computer Science, 595:130-142, 2015. Google Scholar
  44. Farnoosh Khodakarami, Farzad Didehvar, and Ali Mohades. 1.5 d terrain guarding problem parameterized by guard range. Theoretical Computer Science, 661:65-69, 2017. Google Scholar
  45. David G. Kirkpatrick. An O(lg lg OPT)-approximation algorithm for multi-guarding galleries. Discrete & Computational Geometry, 53(2):327-343, 2015. URL: https://doi.org/10.1007/s00454-014-9656-8.
  46. Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Węgrzycki. A gap-eth-tight approximation scheme for euclidean tsp. arXiv preprint, 2020. URL: http://arxiv.org/abs/2011.03778.
  47. Linda Kleist. Planar graphs and faces areas - Area-Universality. PhD thesis, Technische Universität Berlin, 2018. PhD thesis. Google Scholar
  48. Bernhard Kornberger. Why is cgal significantly slower under windows? URL: https://stackoverflow.com/questions/58008543/.
  49. Alexander Kröller, Tobias Baumgartner, Sándor P. Fekete, and Christiane Schmidt. Exact solutions and bounds for general art gallery problems. Journal of Experimental Algorithmics (JEA), 17:2-3, 2012. Google Scholar
  50. Der-Tsai Lee and Arthur K. Lin. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 32(2):276-282, 1986. URL: https://doi.org/10.1109/TIT.1986.1057165.
  51. Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal. The complexity of drawing a graph in a polygonal region. Arxiv, 2018. Graph Drawing 2018. Google Scholar
  52. Colin McDiarmid and Tobias Müller. Integer realizations of disk and segment graphs. Journal of Combinatorial Theory, Series B, 103(1):114-143, 2013. Google Scholar
  53. Nicolai E Mnëv. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In Oleg Y. Viro, editor, Topology and geometry - Rohlin seminar, pages 527-543. Springer-Verlag Berlin Heidelberg, 1988. Google Scholar
  54. 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: https://doi.org/10.1016/0022-0000(90)90017-F.
  55. Joseph O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987. Google Scholar
  56. Jürgen Richter-Gebert and Günter M. Ziegler. Realization spaces of 4-polytopes are universal. Bulletin of the American Mathematical Society, 32(4):403-412, 1995. Google Scholar
  57. Tim Roughgarden. Beyond the worst-case analysis of algorithms (introduction). CoRR, abs/2007.13241, 2020. URL: http://arxiv.org/abs/2007.13241.
  58. Marcus Schaefer. Complexity of some geometric and topological problems. In Proceedings of the 17th International Symposium on Graph Drawing (GD 2009), volume 5849 of Lecture Notes in Computer Science (LNCS), pages 334-344. Springer, 2009. Google Scholar
  59. Marcus Schaefer. Realizability of graphs and linkages. In Thirty Essays on Geometric Graph Theory, pages 461-482. Springer, 2013. Google Scholar
  60. Marcus Schaefer and Daniel Štefankovič. Fixed points, Nash equilibria, and the existential theory of the reals. Theory of Computing Systems, 60(2):172-193, 2017. URL: https://doi.org/10.1007/s00224-015-9662-0.
  61. Dietmar Schuchardt and Hans-Dietrich Hecker. Two NP-hard art-gallery problems for ortho-polygons. Math. Log. Q., 41:261-267, 1995. URL: https://doi.org/10.1002/malq.19950410212.
  62. Yaroslav Shitov. A universality theorem for nonnegative matrix factorizations. arXiv, 2016. URL: http://arxiv.org/abs/1606.09068.
  63. Yaroslav Shitov. The complexity of positive semidefinite matrix factorization. SIAM Journal on Optimization, 27(3):1898-1909, 2017. Google Scholar
  64. Peter Shor. Stretchability of pseudolines is np-hard. Applied Geometry and Discrete Mathematics-The Victor Klee Festschrift, 1991. Google Scholar
  65. The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 4.1.3 edition, 2020. URL: https://doc.cgal.org/4.1.3/Manual/packages.html.
  66. Davi C. Tozoni, Pedro J. de Rezende, and Cid C de Souza. A practical iterative algorithm for the art gallery problem using integer linear programming. Optimization Online, 2013. Google Scholar
  67. Davi C. Tozoni, Pedro J. de Rezende, and Cid C. de Souza. The quest for optimal solutions for the art gallery problem: A practical iterative algorithm. In Experimental Algorithms, pages 320-336, 2013. Google Scholar
  68. Davi C. Tozoni, Pedro J. de Rezende, and Cid C. de Souza. Algorithm 966: A practical iterative algorithm for the art gallery problem using integer linear programming. ACM Trans. Math. Softw., 43(2), 2016. URL: https://doi.org/10.1145/2890491.
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