Document Open Access Logo

Exact Algorithms for Terrain Guarding

Authors Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.11.pdf
  • Filesize: 0.83 MB
  • 15 pages

Document Identifiers

Author Details

Pradeesha Ashok
Fedor V. Fomin
Sudeshna Kolay
Saket Saurabh
Meirav Zehavi

Cite As Get BibTex

Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh, and Meirav Zehavi. Exact Algorithms for Terrain Guarding. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.11

Abstract

Given a 1.5-dimensional terrain T, also known as an x-monotone polygonal chain, the Terrain Guarding problem seeks a set of points of minimum size on T that guards all of the points on T. Here, we say that a point p guards a point q if no point of the line segment pq is strictly below T. The Terrain Guarding problem has been extensively studied for over 20 years. In 2005 it was already established that this problem admits a constant-factor approximation algorithm [SODA 2005]. However, only in 2010 King and Krohn [SODA 2010] finally showed that Terrain Guarding is NP-hard. In spite of the remarkable developments in approximation algorithms for Terrain Guarding, next to nothing is known about its parameterized complexity. In particular, the most intriguing open  questions in this direction ask whether it admits a subexponential-time algorithm and whether it is fixed-parameter tractable. In this paper, we answer the first question affirmatively by developing an n^O(sqrt{k})-time algorithm for both Discrete Terrain Guarding and Continuous Terrain Guarding.  We also make non-trivial progress with respect to the second question: we show that Discrete Orthogonal Terrain Guarding, a well-studied special case of Terrain Guarding, is fixed-parameter tractable.

Subject Classification

Keywords
  • Terrain Guarding
  • Art Gallery
  • Exponential-Time Algorithms

Metrics

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

References

  1. J. Abello, O. Egecioglu, and K. Kumar. Visibility graphs of staircase polygons and the weak bruhat order I: From visibility graphs to maximal chains. Discrete and Computational Geometry, 14(3):331-358, 1995. Google Scholar
  2. Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, 33(4):461-493, 2002. Google Scholar
  3. B. Ben-Moshe, M. J. Katz, and J. S. B. Mitchell. A constant-factor approximation algorithm for optimal 1.5d terrain guarding. SICOMP, 36(6):1631-1647, 2007. Google Scholar
  4. E. Bonnet and T. Miltzow. Parameterized hardness of art gallery problems. In ESA, 2016. Google Scholar
  5. D. Z. Chen, V. Estivill-Castro, and J. Urrutia. Optimal guarding of polygons and monotone chains. In CCCG, pages 133-138, 1995. Google Scholar
  6. K. L. Clarkson and K. R. Varadarajan. Improved approximation algorithms for geometric set cover. Discrete and Computational Geometry, 37(1):43-58, 2007. Google Scholar
  7. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  8. Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM, 52(6):866-893, 2005. Google Scholar
  9. R. Diestel. Graph Theory, 4th Edition. Springer, 2012. Google Scholar
  10. R. Downey and M. R. Fellows. Fundamentals of parameterized complexity. Springer, 2013. Google Scholar
  11. S. Durocher, P. C. Li, and S. Mehrabi. Guarding orthogonal terrains. In CCCG, 2015. Google Scholar
  12. M K Elbassioni, E Krohn, D Matijevic, J Mestre, and D Severdija. Improved approximations for guarding 1.5-dimensional terrains. Algorithmica, 60(2):451-463, 2011. Google Scholar
  13. W. Evans and N. Saeedi. On characterizing terrain visibility graphs. JoCG, 6(1):108-141, 2015. Google Scholar
  14. S. Friedrichs, M. Hemmer, J. King, and C. Schmidt. The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS. JoCG, 7(1):256-284, 2016. Google Scholar
  15. P. Giannopoulos. Open problems: Guarding problems. Lorentz Workshop on Fixed-Parameter Computational Geometry, Leiden, the Netherlands, page 12, 2016. Google Scholar
  16. M. Gibson, G. Kanade, E. Krohn, and K. Varadarajan. Guarding terrains via local search. JoCG, 5(1):168-178, 2014. Google Scholar
  17. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980. Google Scholar
  18. S. K. Gosh. Visibility algorithms in the plane. Cambridge University Press, 2007. Google Scholar
  19. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity. Journal of Computer and System Sciences (JCSS0, 63(4):512-530, 2001. Google Scholar
  20. M. J. Katz and G. S. Roisman. On guarding the vertices of rectilinear domains. Computational Geometry, 39(3):219-228, 2008. Google Scholar
  21. F. Khodakarami, F. Didehvar, and A. Mohades. A fixed-parameter algorithm for guarding 1.5D terrains. Theoretical Computer Science, 595:130-142, 2015. Google Scholar
  22. J. King. A 4-approximation algorithm for guarding 1.5-dimensional terrains. In LATIN, pages 629-640, 2006. Google Scholar
  23. J. King and E. Krohn. Terrain guarding is NP-hard. SICOMP, 40(5):1316-1339, 2011. Google Scholar
  24. Y. Lyu and A. Üngör. A fast 2-approximation algorithm for guarding orthogonal terrains. In CCCG, 2016. Google Scholar
  25. S. Mehrabi. Guarding the vertices of an orthogonal terrain using vertex guards. arXiv:1512.08292, 2015. Google Scholar
  26. J. O'rourke. Art gallery theorems and algorithms. Oxford University Press, 1987. Google Scholar
  27. D. Schuchardt and H. D. Hecker. Two NP-hard art-gallery problems for ortho-polygons. Mathematical Logic Quarterly, 41:261-267, 1995. Google Scholar
  28. J. Urrutia. 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 About DROPS Imprint Privacy Contact