On Orthogonally Guarding Orthogonal Polygons with Bounded Treewidth
- PDF / 1,443,979 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 71 Downloads / 175 Views
On Orthogonally Guarding Orthogonal Polygons with Bounded Treewidth Therese Biedl1 · Saeed Mehrabi2 Received: 2 December 2017 / Accepted: 17 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract There exist many variants of guarding an orthogonal polygon in an orthogonal fashion: sometimes a guard can see within a rectangle, along a staircase, or along an orthogonal path with at most k bends. In this paper, we study all these guarding models for the special case of orthogonal polygons that have bounded treewidth in some sense. As our main result, we show that the problem of finding the minimum number of guards in all these models becomes linear-time solvable on polygons with bounded treewidth. We complement our main result by giving some hardness results. Keywords Art gallery problem · Orthogonal polygons · Treewidth
1 Introduction The art gallery problem is one of the oldest problems studied in computational geometry. In the standard art gallery, introduced by Klee in 1973 [3], the objective is to observe a simple polygon P in the plane with the minimum number of point guards, where a point p ∈ P is seen by a guard if the line segment connecting p to the guard lies entirely inside the polygon. Chvátal [4] proved that ⌊n∕3⌋ point guards are always sufficient and sometimes necessary to guard a simple polygon with Preliminary versions of the results of this paper appeared in at the 27th International Symposium on Algorithms and Computation (ISAAC 2016) [1] and at the 28th Canadian Conference on Computational Geometry (CCCG 2017) [2]. This work is supported in part by NSERC, and was done while the second author was at the University of Waterloo. * Saeed Mehrabi [email protected] Therese Biedl [email protected] 1
Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada
2
School of Computer Science, Carleton University, Ottawa, Canada
13
Vol.:(0123456789)
Algorithmica
p1
p2
g1
g2
(a)
(b)
Fig. 1 a A polygon P with its standard pixelation (black, solid) and its 1-refinement (red, dashed). The gray area indicates a hole. The four points p1 , p2 , g1 and g2 will be referred in the subsequent sections. b The planar graph GΨ corresponding to the polygon shown in a (Color figure online)
n vertices. The art gallery problem is known to be NP-hard on arbitrary polygons [5] and orthogonal polygons [6]. Even severely restricting the shape of the polygon does not help: the problem remains NP-hard for simple monotone polygons [7] and for orthogonal tree polygons (defined precisely below) if guards must be at vertices [8]. Further, the art gallery problem is APX-hard on simple polygons [9], but some approximation algorithms have been developed [7, 10]. A number of other types of guards have been studied, especially for orthogonal polygons. See for example guarding with sliding cameras [11–14], guarding with rectangles [15] or with orthogonally convex polygons [16]. Also, different types of visibility have been studied, especially for orthogon
Data Loading...
