Document Open Access Logo

Universal Guard Problems

Authors Sándor P. Fekete, Qian Li, Joseph S. B. Mitchell, Christian Scheffer

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.32.pdf
  • Filesize: 0.65 MB
  • 13 pages

Document Identifiers

Author Details

Sándor P. Fekete
Qian Li
Joseph S. B. Mitchell
Christian Scheffer

Cite AsGet BibTex

Sándor P. Fekete, Qian Li, Joseph S. B. Mitchell, and Christian Scheffer. Universal Guard Problems. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.32

Abstract

We provide a spectrum of results for the Universal Guard Problem, in which one is to obtain a small set of points ("guards") that are "universal" in their ability to guard any of a set of possible polygonal domains in the plane. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of n vertices, or to guard all polygons in a given set of k polygons on an n-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities.
Keywords
  • Art Gallery Problem
  • universal guarding
  • polygonization
  • worst-case bounds
  • robust covering

Metrics

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

References

  1. Yoav Amit, Joseph S. B. Mitchell, and Eli Packer. Locating guards for visibility coverage of polygons. Int. J. Comp. Geom. Appl., 20(5):601-630, October 2010. Google Scholar
  2. 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 Symp. Comp. Geom. (SoCG'13), pages 347-348, 2013. Google Scholar
  3. H. Brönnimann and M. T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete &Computational Geometry, 14:263-279, 1995. Google Scholar
  4. V. Chvátal. A combinatorial theorem in plane geometry. J. Comb. Th. B, 18:39-41, 1975. Google Scholar
  5. Kenneth L Clarkson. Algorithms for polytope covering and approximation. In Algorithms and Data Structures, pages 246-252. Springer, 1993. Google Scholar
  6. Marcelo C. Couto, Pedro J. de Rezende, and Cid C. de Souza. An exact algorithm for minimizing vertex guards on art galleries. Int. Transact. Op. Res., 18:425-448, 2011. Google Scholar
  7. Alon Efrat and Sariel Har-Peled. Guarding galleries and terrains. Inf. Process. Lett., 100(6):238-245, 2006. Google Scholar
  8. Alon Efrat, Sariel Har-Peled, and Joseph S. B. Mitchell. Approximation algorithms for location problems in sensor networks. In 2nd Int. Conf. Broadband Networks, pages 767-776, 2005. Google Scholar
  9. Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller, and Christiane Schmidt. Facets for art gallery problems. Algorithmica, 73:411-440, 2015. Google Scholar
  10. Sándor P. Fekete, Qian Li, Joseph S. B. Mitchell, and Christian Scheffer. Universal guard problems. CoRR, abs/1611.08315, 2016. URL: http://arxiv.org/abs/1611.08315.
  11. S. Fisk. A short proof of Chvátal’s watchman theorem. J. Comb. Th. B, 24:374, 1978. Google Scholar
  12. Stephan Friedrichs, Michael Hemmer, and Christiane Schmidt. A PTAS for the continuous 1.5d terrain guarding problem. CoRR, abs/1405.6564, 2014. Google Scholar
  13. S. K. Ghosh. Approximation algorithms for art gallery problems. In Proc. Canadian Inform. Process. Soc. Congress, 1987. Google Scholar
  14. Subir Kumar Ghosh. Approximation algorithms for art gallery problems in polygons. Discrete Applied Mathematics, 158(6):718-722, 2010. Google Scholar
  15. Hector Gonzalez-Banos and Jean-Claude Latombe. A randomized art-gallery algorithm for sensor placement. In Proc. 17th Annu. ACM Sympos. Comput. Geom., 2001. Google Scholar
  16. Mohammad T Hajiaghayi, Robert Kleinberg, and Tom Leighton. Improved lower and upper bounds for universal TSP in planar metrics. In Proc. Symp. Disc. Alg. (SODA), pages 649-658, 2006. Google Scholar
  17. F. Hoffmann, M. Kaufmann, and K. Kriegel. The art gallery theorem for polygons with holes. In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages 39-48, 1991. Google Scholar
  18. Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. Universal approximations for TSP, Steiner tree, and set cover. In Symp. Theory Comp. (STOC), pages 386-395, 2005. Google Scholar
  19. J. Mark Keil. Polygon decomposition. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 491-518. Elsevier, Amsterdam, 2000. Google Scholar
  20. James King and David Kirkpatrick. Improved approximation for guarding simple galleries from the perimeter. Discrete &Computational Geometry, 46(2):252-269, 2011. Google Scholar
  21. James King and Erik Krohn. Terrain guarding is NP-hard. SIAM J. Comp., 40(5):1316-1339, 2011. Google Scholar
  22. Erik Krohn, Matt Gibson, Gaurav Kanade, and Kasturi Varadarajan. Guarding terrains via local search. Journal of Computational Geometry, 5(1):168-178, 2014. Google Scholar
  23. Alexander Kröller, Tobias Baumgartner, Sándor P. Fekete, and Christiane Schmidt. Exact solutions and bounds for general art gallery problems. ACM Journal of Experimental Algorithmics, 17(1), 2012. URL: http://dx.doi.org/10.1145/2133803.2184449.
  24. J. O'Rourke. Art Gallery Theorems and Algorithms. The International Series of Monographs on Computer Science. Oxford University Press, New York, NY, 1987. Google Scholar
  25. T. C. Shermer. Recent results in art galleries. Proc. IEEE, 80(9):1384-1399, September 1992. Google Scholar
  26. 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. Optimization Online, January 2013. Google Scholar
  27. C. Worman and M. Keil. Polygon decomposition and the orthogonal Art Gallery Problem. Int. J. Comp. Geom. Appl., 17(2):105-138, 2007. 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