Document Open Access Logo

The Dispersive Art Gallery Problem

Authors Christian Rieck , Christian Scheffer

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.67.pdf
  • Filesize: 1.15 MB
  • 18 pages

Document Identifiers

Author Details

Christian Rieck
  • Department of Computer Science, TU Braunschweig, Germany
Christian Scheffer
  • Faculty of Electrical Engineering and Computer Science, Bochum University of Applied Sciences, Germany

Acknowledgements

We thank Joseph S.B. Mitchell for bringing this problem to our attention.

Cite As Get BibTex

Christian Rieck and Christian Scheffer. The Dispersive Art Gallery Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 67:1-67:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.67

Abstract

We introduce a new variant of the art gallery problem that comes from safety issues. In this variant we are not interested in guard sets of smallest cardinality, but in guard sets with largest possible distances between these guards. To the best of our knowledge, this variant has not been considered before. We call it the Dispersive Art Gallery Problem. In particular, in the dispersive art gallery problem we are given a polygon 𝒫 and a real number 𝓁, and want to decide whether 𝒫 has a guard set such that every pair of guards in this set is at least a distance of 𝓁 apart.
In this paper, we study the vertex guard variant of this problem for the class of polyominoes. We consider rectangular visibility and distances as geodesics in the L₁-metric. Our results are as follows. We give a (simple) thin polyomino such that every guard set has minimum pairwise distances of at most 3. On the positive side, we describe an algorithm that computes guard sets for simple polyominoes that match this upper bound, i.e., the algorithm constructs worst-case optimal solutions. We also study the computational complexity of computing guard sets that maximize the smallest distance between all pairs of guards within the guard sets. We prove that deciding whether there exists a guard set realizing a minimum pairwise distance for all pairs of guards of at least 5 in a given polyomino is NP-complete.
We were also able to find an optimal dynamic programming approach that computes a guard set that maximizes the minimum pairwise distance between guards in tree-shaped polyominoes, i.e., computes optimal solutions; due to space constraints, details can be found in the full version of our paper [Christian Rieck and Christian Scheffer, 2022]. Because the shapes constructed in the NP-hardness reduction are thin as well (but have holes), this result completes the case for thin polyominoes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Art gallery
  • dispersion
  • polyominoes
  • NP-completeness
  • r-visibility
  • vertex guards
  • L₁-metric
  • worst-case optimal

Metrics

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

Related Versions

References

  1. James Abello, Vladimir Estivill-Castro, Thomas C. Shermer, and Jorge Urrutia. Illumination of orthogonal polygons with orthogonal floodlights. International Journal of Computational Geometry and Applications, 8(1):25-38, 1998. URL: https://doi.org/10.1142/S0218195998000035.
  2. Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational guards are sometimes needed. In Symposium on Computational Geometry (SoCG), pages 3:1-3:15, 2017. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.3.
  3. Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is ∃ℝ-complete. Journal of the ACM, 69(1):4:1-4:70, 2022. URL: https://doi.org/10.1145/3486220.
  4. Andreas Bärtschi, Subir Kumar Ghosh, Matús Mihalák, Thomas Tschager, and Peter Widmayer. Improved bounds for the conflict-free chromatic art gallery problem. In Symposium on Computational Geometry (SoCG), pages 144-153, 2014. URL: https://doi.org/10.1145/2582112.2582117.
  5. Andreas Bärtschi and Subhash Suri. Conflict-free chromatic art gallery coverage. Algorithmica, 68(1):265-283, 2014. URL: https://doi.org/10.1007/s00453-012-9732-5.
  6. Christoph Baur and Sándor P. Fekete. Approximation of geometric dispersion problems. Algorithmica, 30(3):451-470, 2001. URL: https://doi.org/10.1007/s00453-001-0022-x.
  7. Marc Benkert, Joachim Gudmundsson, Christian Knauer, René van Oostrum, and Alexander Wolff. A polynomial-time approximation algorithm for a geometric dispersion problem. International Journal of Computational Geometry and Applications, 19(3):267-288, 2009. URL: https://doi.org/10.1142/S0218195909002952.
  8. Therese C. Biedl, Mohammad T. Irfan, Justin Iwerks, Joondong Kim, and Joseph S. B. Mitchell. Guarding polyominoes. In Symposium on Computational Geometry (SoCG), pages 387-396, 2011. URL: https://doi.org/10.1145/1998196.1998261.
  9. Therese C. Biedl, Mohammad T. Irfan, Justin Iwerks, Joondong Kim, and Joseph S. B. Mitchell. The art gallery theorem for polyominoes. Discrete Computational Geometry, 48(3):711-720, 2012. URL: https://doi.org/10.1007/s00454-012-9429-1.
  10. Therese C. Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud. Dispersion for intervals: A geometric approach. In Symposium on Simplicity in Algorithms (SOSA), pages 37-44, 2021. URL: https://doi.org/10.1137/1.9781611976496.4.
  11. Therese C. Biedl and Saeed Mehrabi. On r-guarding thin orthogonal polygons. In Symposium on Algorithms and Computation (ISAAC), pages 17:1-17:13, 2016. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2016.17.
  12. Édouard Bonnet and Panos Giannopoulos. Orthogonal terrain guarding is NP-complete. Journal of Computational Geometry, 10(2):21-44, 2019. URL: https://doi.org/10.20382/jocg.v10i2a3.
  13. Prosenjit Bose, Leonidas J. Guibas, Anna Lubiw, Mark H. Overmars, Diane L. Souvaine, and Jorge Urrutia. The floodlight problem. International Journal of Computational Geometry and Applications, 7(1/2):153-163, 1997. URL: https://doi.org/10.1142/S0218195997000090.
  14. Sergio Cabello. Approximation algorithms for spreading points. Journal of Algorithms, 62(2):49-73, 2007. URL: https://doi.org/10.1016/j.jalgor.2004.06.009.
  15. Paola Cappanera. A survey on obnoxious facility location problems. Technical report, Università di Pisa, 1999. Google Scholar
  16. Barun Chandra and Magnús M. Halldórsson. Approximation algorithms for dispersion problems. Journal of Algorithms, 38(2):438-465, 2001. URL: https://doi.org/10.1006/jagm.2000.1145.
  17. Vasek Chvátal. A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, 18(1):39-41, 1975. URL: https://doi.org/10.1016/0095-8956(75)90061-1.
  18. Jurek Czyzowicz, Eduardo Rivera-Campo, and Jorge Urrutia. Optimal floodlight illumination of stages. In Canadian Conference on Computational Geometry (CCCG), pages 393-398, 1993. Google Scholar
  19. Mark de Berg and Amirali Khosravi. Optimal binary space partitions for segments in the plane. International Journal on Computational Geometry and Applications, 22(3):187-206, 2012. URL: https://doi.org/10.1142/S0218195912500045.
  20. Adrian Dumitrescu and Minghui Jiang. Dispersion in disks. Theory of Computing Systems, 51(2):125-142, 2012. URL: https://doi.org/10.1007/s00224-011-9331-x.
  21. Lawrence H. Erickson and Steven M. LaValle. A chromatic art gallery problem. Technical report, University of Illinois, 2010. Google Scholar
  22. Lawrence H. Erickson and Steven M. LaValle. An art gallery approach to ensuring that landmarks are distinguishable. In Robotics: Science and Systems VII, 2011. URL: https://doi.org/10.15607/RSS.2011.VII.011.
  23. Erhan Erkut and Susan Neuman. Analytical models for locating undesirable facilities. European Journal of Operational Research, 40(3):275-291, 1989. URL: https://doi.org/10.1016/0377-2217(89)90420-7.
  24. Vladimir Estivill-Castro, Joseph O'Rourke, Jorge Urrutia, and Dianna Xu. Illumination of polygons with vertex lights. Information Processing Letters, 56(1):9-13, 1995. URL: https://doi.org/10.1016/0020-0190(95)00129-Z.
  25. Sándor P. Fekete, Stephan Friedrichs, Michael Hemmer, Joseph S. B. Mitchell, and Christiane Schmidt. On the chromatic art gallery problem. In Canadian Conference on Computational Geometry (CCCG), 2014. URL: http://www.cccg.ca/proceedings/2014/papers/paper11.pdf.
  26. Sándor P. Fekete and Henk Meijer. Maximum dispersion and geometric maximum weight cliques. Algorithmica, 38(3):501-511, 2004. URL: https://doi.org/10.1007/s00453-003-1074-x.
  27. Jirí Fiala, Jan Kratochvíl, and Andrzej Proskurowski. Systems of distant representatives. Discrete Applied Mathematics, 145(2):306-316, 2005. URL: https://doi.org/10.1016/j.dam.2004.02.018.
  28. Steve Fisk. A short proof of Chvátal’s watchman theorem. Journal of Combinatorial Theory, 24(3):374, 1978. URL: https://doi.org/10.1016/0095-8956(78)90059-X.
  29. Michael Formann and Frank Wagner. A packing problem with applications to lettering of maps. In Symposium on Computational Geometry (SoCG), pages 281-288, 1991. URL: https://doi.org/10.1145/109648.109680.
  30. Frank Hoffmann. On the rectilinear art gallery problem. In International Colloquium on Automata, Languages and Programming (ICALP), pages 717-728, 1990. URL: https://doi.org/10.1007/BFb0032069.
  31. Frank Hoffmann, Klaus Kriegel, Subhash Suri, Kevin Verbeek, and Max Willert. Tight bounds for conflict-free chromatic guarding of orthogonal art galleries. Computational Geometry, 73:24-34, 2018. URL: https://doi.org/10.1016/j.comgeo.2018.01.003.
  32. Hiro Ito, Hideyuki Uehara, and Mitsuo Yokoyama. NP-completeness of stage illumination problems. In Japanese Conference on Discrete and Computational Geometry (JCDCG), pages 158-165, 1998. URL: https://doi.org/10.1007/978-3-540-46515-7_12.
  33. Chuzo Iwamoto and Tatsuaki Ibusuki. Computational complexity of the chromatic art gallery problem for orthogonal polygons. In Conference and Workshops on Algorithms and Computation (WALCOM), pages 146-157, 2020. URL: https://doi.org/10.1007/978-3-030-39881-1_13.
  34. Minghui Jiang, Sergey Bereg, Zhongping Qin, and Binhai Zhu. New bounds on map labeling with circular labels. In Symposium on Algorithms and Computation (ISAAC), pages 606-617, 2004. URL: https://doi.org/10.1007/978-3-540-30551-4_53.
  35. Jeff Kahn, Maria Klawe, and Daniel Kleitman. Traditional galleries require fewer watchmen. SIAM Journal on Algebraic Discrete Methods, 4(2):194-206, 1983. URL: https://doi.org/10.1137/0604020.
  36. James King and Erik Krohn. Terrain guarding is NP-hard. SIAM Journal on Computing, 40(5):1316-1339, 2011. URL: https://doi.org/10.1137/100791506.
  37. D. T. 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.
  38. Shimin Li and Haitao Wang. Dispersing points on intervals. Discrete Applied Mathematics, 239:106-118, 2018. URL: https://doi.org/10.1016/j.dam.2017.12.028.
  39. Bengt J. Nilsson, David Orden, Leonidas Palios, Carlos Seara, and Pawel Zylinski. Illuminating the x-axis by α-floodlights. In Symposium on Algorithms and Computation (ISAAC), pages 11:1-11:12, 2021. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2021.11.
  40. Joseph O'Rourke. An alternate proof of the rectilinear art gallery theorem. Journal of Geometry, 21(1):118-130, 1983. URL: https://doi.org/10.1007/BF01918136.
  41. Joseph O'Rourke. Art gallery theorems and algorithms. Oxford New York, NY, USA, 1987. Google Scholar
  42. Christian Rieck and Christian Scheffer. The dispersive art gallery problem, 2022. URL: http://arxiv.org/abs/2209.10291.
  43. Dietmar Schuchardt and Hans-Dietrich Hecker. Two NP-hard art-gallery problems for ortho-polygons. Mathematical Logic Quarterly, 41:261-267, 1995. URL: https://doi.org/10.1002/malq.19950410212.
  44. Thomas C. Shermer. Recent results in art galleries (geometry). Proceedings of the IEEE, 80(9):1384-1399, 1992. Google Scholar
  45. William L. Steiger and Ileana Streinu. Illumination by floodlights. Computational Geometry, 10(1):57-70, 1998. URL: https://doi.org/10.1016/S0925-7721(97)00027-8.
  46. Jorge Urrutia. Art gallery and illumination problems. In Handbook of Computational Geometry, pages 973-1027, 2000. URL: https://doi.org/10.1016/b978-044482537-7/50023-1.
  47. Chris Worman and J. Mark Keil. Polygon decomposition and the orthogonal art gallery problem. International Journal on Computational Geometry and Applications, 17(2):105-138, 2007. URL: https://doi.org/10.1142/S0218195907002264.
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 About DROPS Imprint Privacy Contact