Title | ||
---|---|---|
Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs |
Abstract | ||
---|---|---|
In this paper we consider the problem of monitoring an art gallery modeled as a polygon, the edges of which are arcs of curves, with edge or mobile guards. Our focus is on piecewise-convex polygons, i.e., polygons that are locally convex, except possibly at the vertices, and their edges are convex arcs. We transform the problem of monitoring a piecewise-convex polygon to the problem of 2-dominating a properly defined triangulation graph with edges or diagonals, where 2-dominance requires that every triangle in the triangulation graph has at least two of its vertices in its 2-dominating set. We show that: (1) @?n+13@? diagonal guards are always sufficient and sometimes necessary, and (2) @?2n+15@? edge guards are always sufficient and sometimes necessary, in order to 2-dominate a triangulation graph. Furthermore, we show how to compute: (1) a diagonal 2-dominating set of size @?n+13@? in linear time and space, (2) an edge 2-dominating set of size @?2n+15@? in O(n^2) time and O(n) space, and (3) an edge 2-dominating set of size @?3n7@? in O(n) time and space. Based on the above-mentioned results, we prove that, for piecewise-convex polygons, we can compute: (1) a mobile guard set of size @?n+13@? in O(nlogn) time, (2) an edge guard set of size @?2n+15@? in O(n^2) time, and (3) an edge guard set of size @?3n7@? in O(nlogn) time. All space requirements are linear. Finally, we show that @?n3@? mobile or @?n3@? edge guards are sometimes necessary. When restricting our attention to monotone piecewise-convex polygons, the bounds mentioned above drop: @?n+14@? edge or mobile guards are always sufficient and sometimes necessary; such an edge or mobile guard set, of size at most @?n+14@?, can be computed in O(n) time and space. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.comgeo.2010.07.002 | Computational Geometry: Theory and Applications |
Keywords | DocType | Volume |
triangulation graphs,monotone piecewise-convex poly- gons,curvilinear art gallery,diagonal guard,piecewise-convex polygon,edge guards,space requirement,mobile guard,2-dominating set,art gallery,curvilinear polygons,edge guard,triangulation graph,edge 2-dominating set,mobile guards,piecewise-convex polygons,linear time,diagonal guards,2-dominance,mobile guard set,dominating set | Journal | 44 |
Issue | ISSN | Citations |
1 | Computational Geometry: Theory and Applications | 3 |
PageRank | References | Authors |
0.47 | 15 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Menelaos I. Karavelas | 1 | 229 | 18.99 |