文章基本信息

标题：Parameter Analysis for Guarding Terrains
本地全文：下载
作者：Akanksha Agrawal ; Sudeshna Kolay ; Meirav Zehavi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：162
页码：4:1-4:18
DOI：10.4230/LIPIcs.SWAT.2020.4
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Terrain Guarding; Reflex Vertices; Terrain Minima; FPT Algorithm; XP Algorithm; Kernelization