1 Search Results for "Ashok, Pradeesha"


Document
Exact Algorithms for Terrain Guarding

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

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{ashok_et_al:LIPIcs.SoCG.2017.11,
  author =	{Ashok, Pradeesha and Fomin, Fedor V. and Kolay, Sudeshna and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Exact Algorithms for Terrain Guarding}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.11},
  URN =		{urn:nbn:de:0030-drops-71975},
  doi =		{10.4230/LIPIcs.SoCG.2017.11},
  annote =	{Keywords: Terrain Guarding, Art Gallery, Exponential-Time Algorithms}
}
  • Refine by Author
  • 1 Ashok, Pradeesha
  • 1 Fomin, Fedor V.
  • 1 Kolay, Sudeshna
  • 1 Saurabh, Saket
  • 1 Zehavi, Meirav

  • Refine by Classification

  • Refine by Keyword
  • 1 Art Gallery
  • 1 Exponential-Time Algorithms
  • 1 Terrain Guarding

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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