## 2 Sculpture Garden Problem and Applications  
As mentioned previously, the sculpture garden problem can be considered as a special case of an art gallery problem. There are various problems with similarities and differences with the sculpture garden problem. As the sculpture garden problem comes up from localization problems in wireless mobile computing, we wish to determine the position of some devices in a geometric environment. The sculpture garden problem could be used in localization problems in which a wireless device is used to prove that it belongs to a given polygonal environment. In this case, the locators would be simple and can broadcast information inside a certain angle. In this context, the Boolean predicates could be associated with secret keys. Therefore, each angle guard \(g\) could periodically broadcast a secret key \(K\) in its transmission angle  
Figure 1: (**a**) Natural angle guards do not suffice to define the polygon; (**b**) coverage by three guards (formula B.C.D define the polygon) [3]. and consequently the devices in range would have knowledge of this key. The wireless localization problem with natural vertex guards is an NP-hard problem [4; 5]. In another application, namely constructive solid geometry (CSG), we wish to construct a geometric shape from simple combinations of primitive shapes [6]. Solutions to the sculpture garden problem can be used to construct an efficient CSG formula that defines a given polygon \(P\). The prison yard problem seeks a set of guards that can simultaneously see both the interior and exterior of a simple polygon, in which \(\lfloor n/2\rfloor\) guards are sufficient and sometimes necessary (tight bound) [7]. Another related problem is the floodlight illumination problem, in which the vertex angle guards (called floodlights) with angles of 180 should see a simple polygon [8]. Likewise, studies have been conducted on the complexity of illuminating wedges with angle-restricted floodlights placed at a fixed set of points [9]. There is another study on a generalization of the classical problem of the illumination of polygons. [PERSON] et al. [10] modeled a wireless device whose radio signal can penetrate a given number \(k\) of walls (\(k\)-modems) and they studied the minimum number of \(k\)-modems sufficient and sometimes necessary to illuminate monotone and monotone orthogonal polygons. They showed that every monotone polygon with \(n\) vertices can be illuminated with \(\lceil\frac{n-2}{2k+3}\rceil\)\(k\)-modems. [PERSON] et al. [11] developed lower and upper bounds for the number of \(k\)-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons. In one of the applications of the problem, the wireless localization problem is considered to deal with the placement of the smallest number of broadcasting antennas required to satisfy some property within a given polygon. The antennas propagate a unique key within a certain antenna-specific angle of broadcast, so that the set of keys received at any given point is sufficient to determine whether that point is inside or outside the polygon. To ascertain this localization property, a Boolean formula must be produced along with the placement of the antennas. [PERSON] et al. [12; 13] presented an exact algorithm based on integer linear programming for solving the NP-hard natural wireless localization problem. [PERSON] et al. [14] show that \(\lceil n/2\rceil\) point guards are always sufficient and sometimes necessary to guard a piecewise convex art gallery with \(n\) vertices. [PERSON] et al. [15; 16] showed that for monitoring a piecewise-convex polygon with \(n\geq 2\) vertices, \(\lfloor\frac{2n}{3}\rfloor\) vertex guards are always sufficient and sometimes necessary. They also presented a polynomial algorithm for computing the location of guards.