License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.4
URN: urn:nbn:de:0030-drops-122514
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12251/
Go to the corresponding LIPIcs Volume Portal

Agrawal, Akanksha ; Kolay, Sudeshna ; Zehavi, Meirav

Parameter Analysis for Guarding Terrains

pdf-format:
LIPIcs-SWAT-2020-4.pdf (0.9 MB)

Abstract

The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also attracted attention from the viewpoint of Parameterized complexity. In this paper, we focus on the parameterized complexity of Terrain Guarding (both discrete and continuous) with respect to two natural parameters. First we show that, when parameterized by the number r of reflex vertices in the input terrain, the problem has a polynomial kernel. We also show that, when parameterized by the number c of minima in the terrain, Discrete Orthogonal Terrain Guarding has an XP algorithm.

BibTeX - Entry

@InProceedings{agrawal_et_al:LIPIcs:2020:12251,
  author =	{Akanksha Agrawal and Sudeshna Kolay and Meirav Zehavi},
  title =	{{Parameter Analysis for Guarding Terrains}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12251},
  URN =		{urn:nbn:de:0030-drops-122514},
  doi =		{10.4230/LIPIcs.SWAT.2020.4},
  annote =	{Keywords: Terrain Guarding, Reflex Vertices, Terrain Minima, FPT Algorithm, XP Algorithm, Kernelization}
}

Keywords: Terrain Guarding, Reflex Vertices, Terrain Minima, FPT Algorithm, XP Algorithm, Kernelization
Collection: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI