Biedl, Therese ;
Mehrabi, Saeed
On rGuarding Thin Orthogonal Polygons
Abstract
Guarding a polygon with few guards is an old and wellstudied 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 axisaligned rectangle spanned by p and q is inside the polygon.
A simple proof shows that this problem is NPhard 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 socalled dual graph of the polygon is a tree. It was known that finding the minimum set of rguards is polynomial for tree polygons (and in fact for all orthogonal polygons), but the runtime was ~O(n^17). We show here that with a different approach one can find the minimum set of rguards 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 fixedparameter tractable in h + K.
BibTeX  Entry
@InProceedings{biedl_et_al:LIPIcs:2016:6791,
author = {Therese Biedl and Saeed Mehrabi},
title = {{On rGuarding Thin Orthogonal Polygons}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {17:117:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6791},
URN = {urn:nbn:de:0030drops67913},
doi = {10.4230/LIPIcs.ISAAC.2016.17},
annote = {Keywords: Art Gallery Problem, Orthogonal Polygons, rGuarding, Treewidth, Fixedparameter Tractable}
}
2016
Keywords: 

Art Gallery Problem, Orthogonal Polygons, rGuarding, Treewidth, Fixedparameter Tractable 
Seminar: 

27th International Symposium on Algorithms and Computation (ISAAC 2016)

Issue date: 

2016 
Date of publication: 

2016 