Guarding the vertices of thin orthogonal polygons is NP-hard

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Guarding the vertices of thin orthogonal polygons is NP-hard Ana Paula Tomás ∗ DCC & CMUP, Faculdade de Ciências Universidade do Porto, Portugal Abstract An orthogonal polygon of P is called thin if the dual graph of the partition obtained by extending all edges of P towards its interior until they hit the boundary is a tree. We show that the problem of computing a minimum guard set for the vertices of a thin orthogonal polygon is NP-hard either for guards lying on the boundary, or on vertices or anywhere in the polygon. Introduction The classical art gallery problem for a polygon P asks for a minimum set of points G in P such that every point in P is seen by at least one point in G (the guard set). Many variations of art gallery problems have been studied over the years to deal with various types of constraints on guards and dierent notions of visibility. In the general visibility model, two points p and q in a polygon P see each other if the line segment pq contains no points of the exterior of P . The set V(v) of all points of P visible to a point v∈P is the visibility region of v . A guard set G for a set S⊆P is a set of points of P such that S⊆ ∪v∈G V(v) . Two points vi and vj are equivalent for the visibility relation if V(vi)∩S=V(vj)∩S . If V(vj)∩S⊂V(vi)∩S then vi strictly dominates vj , and vi can replace vj in an optimal guard set of S . Guards that may lie anywhere inside P are called point guards whereas vertex guards are restricted to lie on vertices and boundary guards on the boundary. Combinatorial upper and lower bounds on the number of necessary guards are known for specic settings (for surveys, refer to e.g. [8, 10]). The fact that some art gallery problems are NP-hard [5, 9] motivates the design of heuristic and metaheuristic methods for nding approximate solutions and also the study of more specic classes of polygons where some guarding problems may be tractable [1, 2, 3, 6]. In this paper, we address the problem of guarding the vertices of orthogonal polygons, which is known to be NP-hard for generic or- ∗ Email: [email protected]. Research partially supported by the European Regional Development Fund through the programme COMPETE and by the Portuguese Government through the FCT  Fundação para a Ciência e Tecnologia under the project PEst-C/MAT/UI0144/2011. thogonal polygons [4]. We show that the problem is NP-hard also for the family of thin orthogonal polygons , which consists of the orthogonal polygons such that the dual graph of the corresponding grid partition ΠHV (P) is a tree. ΠHV (P) is obtained by adding all horizontal and vertical cuts incident to the reex vertices of P (see Fig. 1). Our proof is inspired in [4] Figure 1: Orthogonal polygons, grid partitions and dual graphs: (a) ΠHV (P) and its dual graph in general; (b) a thin orthogonal polygon; (c) a thin orthogonal polygon that is a path orthogonal polygon. although the need to obtain thin orthogonal polygons led to novel aspects in the construction. The class of thin orthogonal polygons contains the class of thin polyomino trees introduced in [1], for which the authors conjecture that the guarding problem under the general visibility model has a polynomial-time (exact) algorithm. To the best of our knowledge, this problem is open. In [12], we give a linear-time algorithm for computing an optimal vertex guard set for any given path orthogonal polygon (for which the dual graph of ΠHV (P) is a path graph), and prove tight lower and upper bounds of dn/6e and bn/4c for the optimal solution for the subclass where all horizontal and vertical cuts intersect the boundary at Steiner points. Since the thin grid orthogonal polygons belong to this class, our work extends results previously known for the spiral thin grid orthogonal polygons and the MinArea grid orthogonal polygons [6] (for which the minimum vertex guard sets have exactly bn/4c and dn/6e guards) and somehow explains why the MinArea grid orthogonal polygons were considered representative of extremal behaviour [11]. The result that supports our proof allows us to conclude that a minimum guard set for the vertices of a path orthogonal polygon can be found in linear-time. 11 Guarding the vertices of thin orthogonal polygons is NP-hard In rest of the paper, we show that computing a minimum guard set for the vertices of a thin orthogonal polygon (GVTP) is NP-hard, either for boundary guards, vertex guards or point guards. 1 Hardness for boundary guards Theorem 1 GVTP for thin orthogonal polygons is NP-hard for boundary guards. For the proof, we dene a reduction from the vertex-cover problem in graphs ( VC ) to GVTP with boundary-guards. VC , known to be NP-complete, is the problem of deciding whether a graph G= (V, E) has a vertex-cover S of size |S| ≤ k , for k integer. A vertex-cover of G is a subset S⊆V such that for each edge (u, v)∈E , either u∈S , or v∈S , or both. The thin orthogonal polygon we construct for a given graph G= (V, E) is a large square with |E| tiny d-gadgets attached to its bottom. In Fig. 2 we sketch this construction and in Fig. 3 we present the double gadget (d-gadget) dened for the proof. Figure 2: From VC to GVTP with boundary guards: the representation of G= ({u, v, w},{(u, v),(u, w)}) ; the edges of G are mapped to the points uv and uw (that will be replaced by tiny d-gadgets) and the vertices are mapped to the segments u , v and w . We dene the side-length of this square to be L∆ , with L= 1 + 2|V|+ 3|E| and ∆ = 10L . Considering V={v1, v2, . . . , vn} sorted, we denote by E+ i the subset of all edges (vi, vj)∈E such that i < j , also sorted by increasing value of j . In the construction we follow these orderings: for each i , we represent vi by a segment of length ∆ on the top edge of the square and the edges in E+ i as middle points of |E+ i| consecutive segments of length 2∆ on the bottom edge, placed between the projections of vi and vi+1 , and with separation gaps of length ∆ between each other. The square is implicitly divided into L slabs of length ∆ , and we leave the rst slab empty and an empty slab between consecutive items. Figure 3: A sketch of the d-gadget Ξij dened for the edge (vi, vj) . The vertices on the left side are labelled from N1 to N18 in CW order and on the right side are labelled from M1 to M18 in CCW order. B≡N11 and A≡M11 are the two distinguished vertices. The d-gadget associated to the edge (vi, vj)∈E+ i , denoted by Ξij , is dened as follows. Let Oij be the point that represents the edge (vi, vj) and AiBi and AjBj the segments associated to vi and vj . Together with Oij , these segments dene two visibility cones with apex Oij . By a slight perturbation, we can decouple the two cones, and move the new apexes to the distinguished vertices ( B and A ) of a tiny dgadget Ξij . The structure of this gadget will x segment AiBi (resp. AjBj ) as the portion of the boundary of the polygon that A (resp. B ) sees above line X (i.e, above the gadget). We use VC instead of the minimum 2-interval piercing problem used in [4] in order to be able to control the aperture of visibility cones and also the structure of the thin orthogonal polygon obtained in the reduction. Some of the vertices of a d-gadget can only be guarded by a local guard (i.e., a guard below line X ), for instance, the vertices M16 , M12 , M8 , M7 and M5 on its right part and N16 , N12 , N8 , N7 and N5 on the left part. For every d-gadget, at least three local boundary-guards will be needed to guard these vertices and no three such guards can see both A and B if they see all these vertices. Moreover, one can always locate three local boundary-guards that see all the gadget vertices other than A (namely, at N8 , N1 and M8 ) or other than B (namely, at N8 , M1 and M8 ). Another guard is required to guard the unguarded vertex but it does not need to be local. As we will see, this guard can be located on the portion of the top edge of the polygon seen from the unguarded vertex. We dene the coordinates of the vertices of Ξij w.r.t. a cartesian system ROij with origin at Oij . By construction, the x-coordinates of the points Ai , Bi and Oij w.r.t. a cartesian system xed at the bottom left corner of the large square are given by x0 Ai= (2i−1+3Pk<i |E+ k|)∆ x0 Bi=x0 Ai+ ∆ x0 Oij =x0 Bi+ 2∆ + 3∆ |E+ i∩ {(vi, vj0) : j0< j}| 12 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 and, consequently, if we dene xi and xj as xi= (x0 Oij −x0 Bi)/∆ and xj= (x0 Aj−x0 Oij )/∆ , then, w.r.t. the cartesian system ROij , we have Ai= (−(xi+ 1)∆, L∆) Aj= (xj∆, L∆) Bi= (−xi∆, L∆) Bj= ((xj+ 1)∆, L∆) for integers xi≥2 and xj≥2 . Then, we dene A and B as the intersection points of the supporting lines of −−−→ OijAi and −−−→ OijBj with the line y=−4L , that is, as A= (4xi+ 4,−4L) and B= (−4xj−4,−4L) . So, the rays −−→ AAi and −−→ BBj share the supporting lines of the initial rays −−−→ OijAi and −−−→ OijBj . The aperture of the visibility cone CA=cone(A, AiBi) is determined by the vertices M1 and M13 . We selected M1 as the intersection of −−→ AAi with the line y=−2L and M13 as the intersection of −−→ ABi with the line y=−3L . Therefore, M1= (2xi+2,−2L) and M13 = (τi,−3L) , with τi= 3xi+ 3 + ∆ ∆+4 , because the straight lines AAi and ABi are given by the following equations. AAi:y=−L xi+ 1x ABi:y=−L(∆ + 4) xi(∆ + 4) + 4x+4L∆ xi(∆ + 4) + 4 Similarly, the vertices N1 and N13 determine the aperture of the visibility cone CB=cone(B, AjBj) , being N1= (−2xj−2,−2L) the intersection of −−→ BBj with y=−2L and N13 = (˜τj,−3L) the intersection of −−→ BAj with y=−3L , with ˜τj=−3xj−3−∆ ∆+4 . The coordinates of the vertices of Ξij are M1= (2xi+ 2,−2L)M2= (2xi+ 2,−4L) M3= (2xi+ 1,−4L)M4= (2xi+ 1,−3L) M5= (2xi,−3L)M6= (2xi,−6L) M7= (2xi+ 1,−6L)M8= (2xi+ 1,−5L) M9= (τi,−5L)M10 = (τi,−4L) A= (4xi+ 4,−4L)M12 = (4xi+ 4,−3L) M13 = (τi,−3L)M14 = (τi,−2L) M15 = (7L, −2L)M16 = (7L, −L) M17 = (2xi+ 2,−L)M18 = (2xi+ 2,0) with the Nk= (−αxj−β, γ) i Mk= (αxi+β, γ) , for 1≤k≤18 . Therefore, the coordinates of the vertices can be dened by rational numbers represented by pairs of integers bounded by a quadratic polynomial function on the size of the graph. We can prove that: the dual graph of the grid partition of the resulting polygon is a tree; M16 , M12 , M8 , M7 , M5 , and N16 , N12 , N8 , N7 and N5 require local guards; the boundary of Ξij imposes no restriction on the propagation of the corresponding visibility cones CA and CB ; the unique point on the boundary of Ξij that sees both A and N16 is M1 (similar for B , M16 and N1 ); the three local guards N8 , N1 and M8 jointly see all the gadget vertices other than A (similar for N8 , M1 and M8 and B ). Lemma 2 states the nal result we need to conclude the proof and can be shown as Lemma 2.2. of [4]. Lemma 2 The thin orthogonal polygon P that is obtained can be guarded by 3|E|+k boundary guards if and only if the there is a vertex-cover of size k for the instance graph G= (V, E) . 2 Hardness for vertex guards Theorem 3 GVTP is NP-hard for thin orthogonal polygons with vertex guards. For the proof, we can adapt the previous construction, following the idea of [4], as sketched in Fig. 4. Figure 4: The reduction from VC to GVTP with vertex guards for G= ({u, v, w},{(u, v),(u, w)}) . Ear gadgets are attached to the right endpoints of the segments. Each ear gadget requires a local guard on a vertex of the shaded region (to guard Z2 ). We consider the polygon obtained previously and attach a tiny ear gadget to the right endpoint of each line segment AiBi , for each vi∈V . The local vertices of the ear gadget attached to Bj , w.r.t. the cartesian system xed at the bottom left corner of the large square, can be dened as Z1= ((x0 j+ 1)∆, L(∆ + 1) + 1) Z3= ((x0 j+ 1)∆ + 1, L(∆ + 1)) Z2= ((x0 j+ 1)∆ + L, L(∆ + 1)) and ((x0 j+ 1)∆ + L, L(∆ + 1) + 1) . The separation slabs guarantee that the dual graph of ΠHV (P) for the new polygon P is still a tree, as required. The ear gadgets are dened in such a way that the vertex A of Ξij cannot see any vertex of an ear-gadget except for Bi . Otherwise, A would see points on the boundary of P arbitrarily closed to Bi but to the right of Bi , which is impossible by the denition of the visibility cone CA . The height of the ear gadget prevents B from 13 Guarding the vertices of thin orthogonal polygons is NP-hard seeing any local vertex of the ear-gadget attached to AjBj . For each j≥2 , it is sucient to guarantee that, for all Ξij , the intersection point of the ray −−→ BBj with the vertical edge incident to the vertex labeled Z3 is below Z3 . This holds for all i if it holds for B in the rightmost d-gadget Ξi0j , since the rays −−→ BBj are sorted by slope around Bj . Each ear-gadget needs a local guard that must be located in one of the vertices of the shaded region and none of these vertices sees a local vertex of a dgadget. This means that these guards cannot replace any guard located in a segment. Since any guard located on a segment can move to the segment right endpoint to become a vertex-guard, without loss of visibility, we can adapt the proof of Lemma 2 to show Lemma 4. Lemma 4 The thin orthogonal polygon P that is obtained can be guarded by |V|+3|E|+k boundary guards if and only if the there is a vertex-cover of size k for the instance graph G= (V, E) . 3 Hardness for point guards Theorem 5 GVTP is NP-hard for thin orthogonal polygons with point guards. For the proof, we construct a reduction from the minimum line cover problem ( MLCP ), as in [4]. MLCP is NP-hard [7]. Given a set L={l1, . . . , ln} of lines in the plane, MLCP is the problem of nding a set of points of minimum cardinality such that each line l∈ L contains at least one point in that set. Without loss of generality, we consider that L contains neither vertical nor horizontal lines. The polygon constructed for the reduction is obtained by attaching single-gadgets (called s-gadgets ) to a bounding box B(L) that contains all intersection points of pairs of lines in L in its interior. The idea of this construction is sketched in Fig. 5. Figure 5: The reduction from MLCP to GVTP with guards anywhere. Each tiny box on the bottom represents an s-gadget (note that not all lines intersected the bottom edge of the dashed bounding box). On the right, an s-gadget in detail (the vertices are labelled from M1 to M14 , in CCW order, A≡M11 ). In order to guarantee that a thin orthogonal polygon is obtained, we dene a new type of s-gadget, sketched on Fig. 5, where M1 and M13 reduce the visibility cone CA to the line LA . Moreover, we had to restrict the locations of s-gadgets to the bottom edge of B(L) , in contrast to [4]. This can be done because, for a suciently large bounding box, all lines will intersect the bottom edge of B(L) , as there are no horizontal lines in L . At least a local guard is needed for each s-gadget. As for the d-gadgets, taking into account the relative positions of intersections of the lines with the bottom line (i.e., of vertices M1 ), and their slopes, we can dene the vertices of the tiny sgadget in such a way that M8 sees M12 and M7 , and all local vertices except for A . We can conclude that the vertices of P can be guarded by n+k guards if and only if there is a cover for L of size k . References [1] T. Biedl, M. T. Irfan, J. Iwerks, J. Kim and J. S. Mitchell, Guarding polyominoes, in: Proc. SoCG 2011 , ACM, 2011, 387396. [2] A. Bottino and A. Laurentini, A nearly optimal algorithm for covering the interior of an art gallery, Pattern Recognition 44 (2011), 10481056. [3] M. C. Couto, P. J. de Rezende, and C. C. de Souza, An exact algorithm for minimizing vertex guards on art galleries, Int. T. Oper. Res. 18 (2011), 425  448. [4] M. J. Katz and G. S. Roisman, On guarding the vertices of rectilinear domains, Computational Geometry  Theory and Applications 39 (2008), 219228. [5] D. T. Lee and A. K. Lin, Computational complexity of art gallery problems, IEEE Transactions on Information Theory 32 (1986), 276282. [6] A. M. Martins and A. Bajuelos, Vertex guards in a subclass of orthogonal polygons, Int. J. Computer Science and Network Security , 6 (2006), 102108. [7] N. Megiddo and A. Tamir, On the complexity of locating facilities in the plane, Oper. Res. Lett. 1 (1982), 194197. [8] J. O'Rourke, Art Gallery Theorems and Algorithms , Oxford University Press, 1987. [9] D. Schuchardt and H. Hecker, Two NP-hard problems for ortho-polygons, Math. Logiv. Quart. 41 (1995), 261267. [10] J. Urrutia, Art gallery and illumination problems, in: J.-R. Sack and J. Urrutia (eds), Handbook on Computational Geometry . Elsevier, 2000. [11] A. P. Tomás, A. Bajuelos and F. Marques, On visibility problems in the plane  solving minimum vertex guard problems by sucessive approximations, in: Proc. Int. Symp. Articial Intelligence and Mathematics (ISAIM) , Florida, 2006. [12] A. P. Tomás. Guarding path orthogonal polygons, DCC&CMUP, Univ. Porto, 2013 (in prep). 14