文章基本信息

标题：On r-Guarding Thin Orthogonal Polygons
本地全文：下载
作者：Therese Biedl ; Saeed Mehrabi
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：64
页码：17:1-17:13
DOI：10.4230/LIPIcs.ISAAC.2016.17
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Guarding a polygon with few guards is an old and well-studied problem in computational geometry. Here we consider the following variant: We assume that the polygon is orthogonal and thin in some sense, and we consider a point p to guard a point q if and only if the minimum axis-aligned rectangle spanned by p and q is inside the polygon. A simple proof shows that this problem is NP-hard on orthogonal polygons with holes, even if the polygon is thin. If there are no holes, then a thin polygon becomes a tree polygon in the sense that the so-called dual graph of the polygon is a tree. It was known that finding the minimum set of r-guards is polynomial for tree polygons (and in fact for all orthogonal polygons), but the run-time was ~O(n^17). We show here that with a different approach one can find the minimum set of r-guards can be found in tree polygons in linear time, answering a question posed by Biedl et al. (SoCG 2011). Furthermore, the approach is much more general, allowing to specify subsets of points to guard and guards to use, and it generalizes to polygons with h holes or thickness K, becoming fixed-parameter tractable in h + K.
关键词：Art Gallery Problem; Orthogonal Polygons; r-Guarding; Treewidth; Fixed-parameter Tractable