{'fraction_non_alphanumeric': 0.04883405026035771, 'fraction_numerical': 0.016096898347294542, 'mean_word_length': 3.716604378003203, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Facets for Art Gallery Problems

The Art Gallery Problem (AGP) asks for placing a minimum number of stationary guards in a polygonal region P, such that all points in P are guarded. The problem is known to be NP-hard, and its inherent continuous structure (with both the set of points that need to be guarded and the set of points that can be used for guarding being uncountably infinite) makes it difficult to apply a straightforward formulation as an Integer Linear Program. We use an iterative primal-dual relaxation approach for solving AGP instances to optimality. At each stage, a pair of LP relaxations for a finite candidate subset of primal covering and dual packing constraints and variables is considered; these correspond to possible guard positions and points that are to be guarded. Particularly useful are cutting planes for eliminating fractional solutions. We identify two classes of facets, based on Edge Cover and Set Cover (SC) inequalities. Solving the separation problem for the latter is NP-complete, but exploiting the underlying geometric structure, we show that large subclasses of fractional SC solutions cannot occur for the AGP. This allows us to separate the relevant subset of facets in polynomial time. We also characterize all facets for finite AGP relaxations with coefficients in {0, 1, 2}. Finally, we demonstrate the practical usefulness of our approach. Our cutting plane technique yields a significant improvement in terms of speed and solution quality due to considerably reduced integrality gaps as compared to the approach by Kr\"oller et al.


Introduction
The Art Gallery Problem (AGP) is one of the classical problems of geometric optimization: given a polygonal region P with n vertices, find as few stationary guards as possible, such that any point of the region is visible by at least one of the guards. As first proven by Chvátal [5] and then shown by Fisk [11] in a beautiful and concise proof (which is highlighted in the shortest chapter in "Proofs from THE BOOK" [1]), n 3 guards are sometimes necessary and always sufficient when P is a simple polygon. Worst-case bounds of this type are summarized under the name "Art-Gallery-type theorems", and used as a metaphor even for unrelated problems; see O'Rourke [15] for an early overview, and Urrutia [18] for a more recent survey.
Algorithmically, the AGP is closely related to the Set Cover (SC) problem: All points in P have to be covered by star-shaped subregions of P . The AGP is NP-hard, even for a simply connected polygonal region P [14]. However, the SC problem has no underlying geometry, and it is well known that geometric variants of problems may be easier to solve or approximate than their discrete, graph-theoretic counterparts, so it is natural to explore ways to exploit the geometric nature of the AGP. But the AGP is far from being easily discretized, as both the set to be covered (all points in P ) as well as the covering family (all star-shaped subregions around some point of P ) usually are uncountably infinite.
It is natural to consider more discrete versions of the AGP. Ghosh [12] showed that restricting possible guard positions to the n vertices, i.e., the AGP with vertex guards, allows an O(log n)-approximation algorithm of complexity O(n 5 ); conversely, Eidenbenz et al. [10] showed that for a region with holes, finding an optimal set of vertex guards is at least as hard as SC, so there is little hope of achieving a better approximation guarantee than Ω(log n). While these results provide tight bounds in terms of approximation, they do by no means close the book on the arguably most important aspect of mathematical optimization: combining structural insights with powerful mathematical tools in order to achieve provably optimal solutions for instances of interesting size. Moreover, even a star-shaped polygon may require a large number of vertex guards, so general AGP instances may have significantly better solutions than the considerably simpler discretized version with vertex guards.
Solving AGP Instances. Computing optimal solutions for general AGP instances is not only relevant from a theoretical point of view, but has also gained in practical importance in the context of modeling, mapping and surveying complex environments, such as in the fields of architecture or robotics and even medicine, which are seeking to exploit the ever-improving capabilities of computer vision and laser scanning. Amit, Mitchell and Packer [2] have considered purely combinatorial primal and dual heuristics for general AGP instances. Only very recently have researchers begun to combine methods from integer linear programming with non-discrete geometry in order to obtain optimal solutions. As we showed in [13], it is possible to combine an iterative primal-dual relaxation approach with structures from computational geometry in order to solve AGP instances with unrestricted guard positions; this approach is based on considering a sequence of primal and dual subproblems, each with a finite number of primal variables (corresponding to guard positions) and a finite number of dual variables (corresponding to "witness" positions). Couto et al. [9,8,7] and Tozoni et al. [17] used a similar approach for the AGP with vertex guards. The algorithm in [17] computes lower and upper bounds for the AGP, based on computing finite set-cover instances with the help of a state-of-the-art IP solver. To generate a lower bound, a finite set of witness candidates is chosen and a restricted AGP is solved, in which only the witnesses have to be covered. For this, it suffices to extract a finite set of potential guard positions from the visibility arrangement of the witness set in order to ensure optimality. Similarly, finite sets of potential witness positions for a given finite guard set can be extracted from the visibility arrangment of the guards. This allows it to compute upper and lower bounds for the optimal AGP value by solving discrete set cover instances. The algorithm of [17] iterates between generating tighter lower and upper bounds by refining the witness and guard candidate sets along the iterations. It stops when lower and upper bounds coincide. Although no theoretical convergence has been established, in tests, the approach is able to yield optimal solutions for a large variety of instance classes, even for polygons with up to a thousand vertices.
An approach presented in [13] considers a similar primal-dual scheme, but focuses on the linear relaxation of the primal guard cover, whose dual is the witness packing problem. This forms the basis of the approach presented in this paper; more details are described in Section 3. Furthermore, we have collaborated with the authors of [9,8,7,17] and produced a video [4] that highlights and illustrates the approaches to the AGP, and also demonstrates its relevance for practical applications.
Set Cover. Also important for the work on the AGP is the discrete and finite problem of covering a given set of objects by a an inexpensive collection of subsets. This is known as the Set Cover Problem (SC), which has enjoyed a considerable amount of attention. Highly relevant for the purposes of this paper is the work by Balas and Ng [3] on the discrete SC polytope, which describes all its facets with coefficients in {0, 1, 2}.
Our Results. In this paper, we extend and deepen our recent work on iterative primal-dual relaxations, by proving a number of polyhedral properties of the resulting AGP polytopes. We provide the first study of this type, and give a full characterization of all facets with coefficients 0, 1, and 2. Remarkably, we are able to exploit geometry to prove that only a very restricted family of facets of the general SC polytope will typically have to be used as cutting planes for removing fractional variables. Instead, we are able to prove that many fractional solutions only occur in intermittent SC subproblems; Figure 1 An optimal fractional solution of value 5 without (left) and an optimal integer solution of value 6 with cutting planes (right). Circles show guards, fill-in indicates fractional amount. Cutting planes enforce at least two guards in the left and three in the right area, both marked in grey. thus, they simply vanish when new guards or witnesses are introduced. This saves us the trouble of solving an NP-complete separation problem. Computational results illustrate greatly reduced integrality gaps for a wide variety of benchmark instances, as well as reduced solution times. Details are as follows. Related SC results are described by Balas et al. [3].
-We show how to employ cutting planes for an iterative primal-dual framework for solving the AGP. This is interesting in itself, as it provides an approach to tackling optimization problems with infinitely many constraints and variables. The particular challenge is to identify constraints that remain valid for any choice of infinitely many possible primal and dual variables, as we are not solving one particular IP, but an iteratively refined sequence. -Based on a geometric study of the involved SC constraints, we characterize all facets of involved AGP polytopes that have coefficients in {0, 1, 2}. In the SC setting, these facets are capable of cutting off fractional solutions, but the separation problem is NP-complete. We use geometry to prove that only some of these facets are able to cut off fractional solutions in an AGP setting under reasonable assumptions, allowing us to solve the separation problem in polynomial time. -We provide a class of facets based on Edge Cover (EC) constraints.
-We demonstrate the practical usefulness of our results by showing greatly improved solution speed and quality for a wide array of large benchmarks.

Preliminaries
We consider a polygonal region P with n vertices that may have holes, i.e., that does not have to be simply connected. For a point p ∈ P , we denote by V(p) the visibility polygon of p in P , i.e., the set of all q ∈ P , such that the straight-line connection pq lies completely in P . P is star-shaped if P = V(p) for some p ∈ P . The set of all such points is the kernel of P . For a set S ⊆ P , The AGP asks for a guard cover of minimum cardinality c; this is the same as covering P by a minimum number of star-shaped sub-regions of P . Note that Chvátal's Watchman Theorem [6] guarantees c ≤ n 3 . For simplicity, we abbreviate x(G) := g∈G x g , for any vector x.

Mathematical-Programming Formulation and LP-Based Solution Procedure
In order to keep this work self-contained, we briefly recapitulate our previously published [13] LP formulations of the AGP as well as how to use them to obtain fractional optimal Art Gallery solutions. Then we motivate the necessity to integrate cutting planes to cut off those fractional solutions in order to obtain binary ones. Furthermore, we specify requirements for cutting planes, allowing us to seamlessly integrate them in our framework.
Let P be a polygon and G, W ⊆ P sets of points for possible guard locations and witnesses, i. e., points to be guarded, respectively. We assume W ⊆ V(G). The AGP that covers W using only guards in G can be formulated as an IP denoted by AGP(G, W ): where the original AGP is AGP(P, P ). Chvátal's Watchman Theorem [6] guarantees that only a finite number of variables in AGP(P, P ) are non-zero, but it still has uncountably many variables and constraints, so it cannot be solved directly. Thus we consider finite G, W ⊂ P and solve AGP(G, W ). For dual separation and to generate lower bounds, we require the LP relaxation AGR(G, W ) obtained by relaxing the integrality constraint (3) to: The relation between a solution of AGR(G, W ) and AGR(P, P ) is not obvious, see Figure 2 for the following argumentation. In [13], we show that AGR(P, P ) can be solved optimally for many problem instances by using finite G and W . The procedure uses primal/dual separation (i. e., cutting planes and column generation) to connect AGR(G, W ) to AGR(P, P ): For some finite sets G and W , we solve AGR(G, W ) using the simplex method. This produces an optimal primal solution x * and dual solution y * with objective value z * . The primal is a minimum covering of W by the guards in G, the dual a maximum packing of witnesses in W , such that each guard in G sees at most one of them. We analyze x * and y * as follows: 1. If there exists a point w ∈ P \W with x * (G∩V(w)) < 1, then w corresponds to an inequality of AGR(P, P ) that is violated by x * . The new witness w O O Figure 2 The AGP and its relaxations for G, W ⊆ P . Dotted arrows represent which conclusions may be drawn from the primal and dual solutions x * and y * .
is added to W , and the LP is re-solved. If such a w cannot be found, then x * is optimal for AGR(G, P ), and z * is an upper bound for AGR(P, P ). 2. If there exists a point g ∈ P \G with y * (W ∩V(g)) > 1, then it corresponds to a violated dual inequality of AGR(P, P ). We create the LP column for g and re-solve the LP. If such a g does not exist, y * is an optimal dual solution for AGR(P, W ) and z * is a lower bound for AGR(P, P ).
Both separation problems can be solved efficiently using the overlay of the visibility polygons of all points g ∈ G with x * g > 0 (for the primal case) and all w ∈ W with y * w > 0 (for the dual case), which decomposes P into a planar arrangement of bounded complexity.
Should the upper and the lower bound meet, we have an optimal solution of AGR(P, P ), but AGR(P, P ) is the LP relaxation of AGP(P, P ), so its optimal solution may contain fractional guard values [13], compare Fig. 1. At this point, it is possible to solve AGP(G, P ) using primal separation only, which produces binary upper bounds; but they do not necessarily match the lower bounds, which are still obtained using the relaxation. This scenario can prevent our procedure from terminating, even if it found an optimal Art Gallery solution, because it might be unable to prove its optimality. In the remainder of this paper, we explore the use of cutting planes to cut off large classes of fractional solutions obtained by a procedure like the one described above, increasing lower bounds and enhancing integrality.
To achieve that, we use cutting planes α. Recall that AGP(P, P ) has an infinite number of both variables and constraints. That means that it is not enough for α to be feasible for AGP(G, W ) for the current iteration's finite sets G and W ; α must remain feasible in all future iterations of our algorithm. Formally, feasibility for AGP(G, W ) is insufficient; instead, we require α not to cut off any x ∈ {0, 1} G for an arbitrary P ⊇ G ⊃ G, such that x is feasible for AGP(G , P ). An LP with a set A of such additional constraints is denoted by AGR(G, W, A), its IP counterpart by AGP(G, W, A). Note that AGP(G, P ) Figure 3 Polygon and witness selection S = {w 1 , w 2 , w 3 , w 4 }. Guards located in J 2 can cover all of S, and those in J 1 some part of it, while those in J 0 cover none of S. and AGP(G, P, A) are equivalent. By AGP(G, W ), we sometimes denote the set of its feasible solutions rather than the IP itself, as in conv(AGP(G, W )).

Set Cover Facets
For finite sets of guards and witnesses G, W ⊂ P , AGP(G, W ) is an SC polytope. This motivates the investigation of SC-based facets. In this section, we discuss a family of SC-based facets inspired by Balas et al. [3] and show that their separation, while NP-complete in the SC setting, can, under reasonable assumptions, be solved in polynomial time when exploiting the underlying geometry of the AGP. Additionally, we present a complete list of all AGP facets only using coefficients in {0, 1, 2}.

A Family of Facets
Let P be a polygon and G, W ⊂ P finite sets of guard and witness positions. Consider a finite non-empty subset ∅ ⊂ S ⊆ W of witness positions; the overlay of visibility regions of S is called α S . It implies the partition P = J 0∪ J 1∪ J 2 , cf. Fig. 3; this is analogous to what Balas and Ng [3] did for the SC polytope. Every feasible solution of the AGP has to cover S. Thus, it takes one guard in J 2 , or at least two guards in J 1 to cover S. For any G, this induces the following constraint (5); for the sake of simplicity, we will also refer to this by α S .
In the context of our iterative algorithm, it is important to represent α S independently from G. This is achieved by storing the visibility overlay of the witnesses in S, which implicitly makes the regions J 0 , J 1 and J 2 available. Any guard g ∈ J i in current or future iterations simply gets the coefficient i.
Sufficient coverage of S is necessary for sufficient coverage of P , so (5) is valid for any x ∈ {0, 1} G that is feasible for AGP(G, P ), thus fulfilling our requirement of remaining feasible in future iterations. However, covering S may require more than two guards in J 1 , so (5) does not always provide a supporting hyperplane of conv(AGP(G, W )).
When choosing a single witness S = {w}, we obtain J 2 = V(w), J 1 = ∅ and J 0 = P \ V(w). The resulting constraint is Ineq. (2), the witness-induced constraint of w, multiplied by two. For a choice of S with two witnesses, S = {w 1 , w 2 }, constraint (5) yields the sum of the witness-induced constraints of w 1 and w 2 . Thus, we consider |S| ≥ 3 in the remainder of this section.
In order to show when (5) defines a facet of conv(AGP(G, W )), we first need to apply a result of [3] to the AGP setting.
Proof. We start by proving necessity. If every witness is seen by at least two guards, the |G| vectors x i = 1 − e i are linearly independent and feasible solutions of so there cannot be more than |G| − 1 linearly independent solutions, and conv(AGP(G, W )) is not full-dimensional.
We require some terminology adapted from [3]. Two guards g 1 , g 2 ∈ J 1 are a 2-cover of α S , if S ⊆ V(g 1 ) ∪ V(g 2 ). The 2-cover graph of G and α S is the graph with nodes in J 1 ∩G and an edge between g 1 and g 2 iff g 1 , g 2 are a 2-cover of α S . In addition, we have Theorem 1 Given a polygon P and finite G, W ⊂ P , let conv(AGP(G, W )) be full-dimensional and let α S be as defined in (5), such that S is maximal, i. e., there is no w ∈ W \ S with V(w) ⊆ V(S). Then the constraint induced by α S defines a facet of conv(AGP(G, W )), if and only if: 1. Every component of the 2-cover graph of α S and G has an odd cycle.

For every
Proof. G and W are finite, so AGP(G, W ) is an instance of SC with universe W and subsets G, while conv(AGP(G, W )) describes a full-dimensional SC polytope. Our claim follows from Theorem 2.6 of Balas et al. [3], because the conditions as well as the notion of 2-cover graphs and T are equivalent. The only difference is that we need to intersect J i with G in order to obtain finite sets, as our J i is a region in P , while that of Balas et al. already is a finite set of variables.

Geometric Properties of α S
It is easy to construct SC instances for any choice of |S| ≥ 3, such that the SC version of α S cuts off a fractional solution [3]. Finding α S in the SC setting is NP-complete, see below. But in the following, we show that in an AGP setting, only α S with |S| = 3 actually plays a role in cutting off fractional solutions under reasonable assumptions, allowing us to separate it in polynomial time.
Lemma 2 Let P be a polygon, G, W ⊂ P finite sets of guard and witness positions and ∅ ⊂ S ⊆ W . If every guard in J 1 ∩ G belongs to some 2-cover of α S and S is minimal for G, i. e., there is no proper subset T ⊂ S such that α T and α S induce the same constraint for G, the matrix of AGP(G, S) contains a permutation of the full circulant of order k = |S|, which is Proof. As G and W are finite, conv(AGP(G, W )) is an SC polytope with universe W and subsets G. Then, as above, the claim follows from Balas et al. or, or more accurately, from Theorem 3.1 of [3]: Our definition of S being minimal for G complies with the definition of a minimal C-equivalent subset in [3]; the notion of matrix A J1 S corresponds to our AGP(J 1 ∩ G, S), i. e., a submatrix of AGP(G, S).
Lemma 2 holds, because the 2-cover property holds iff no guard's coefficient in α S can be reduced without turning Ineq. (5) invalid [3]. As S is minimal, removing w from S must increase coefficients, i. e., reclassify a guard g ∈ J 1 ∩G to J 2 . So V(g) ∩ S = S \ {w}. Such a guard exists for every w ∈ S.
Lemma 2 also states that separating α S is equivalent to finding permutations of C k−1 k in the LP matrix of AGR(G, W ). It is possible to reduce a simple graph's adjacency matrix to a polygon with guards G and witnesses W , such that AGR(G, W ) contains a permutation of C k−1 k iff the graph contains a clique of size k or higher: Introduce a guard and a witness for each vertex, place all of them into a convex polygon, and add a hole between a guard and a witness if they represent the same vertex or if the two vertices are not connected.
In the following, we examine when the separation of α S is useful for our iterative algorithm. As α S is represented by one or several permutations of (left) and two attempts for P 3 4 (middle and right). In the left case, Ineq. (5) enforces using two guards instead of three 1 2 -guards. The first attempt for P 3 4 (middle) is star-shaped; here a cutting plane would cut off the intermediate fractional solution of four 1 3 -guards, but as soon as g * is found, the fractional solution is replaced by a binary one with just one guard, with or without cutting plane. Finally, the second attempt for P 3 4 (right) is not star-shaped, but again, there is no need for a cutting plane to cut off the fractional solution of four 1 3 -guards: w * is only covered by 2 3 , so w * is separated by our algorithm and then enforces the use of at least two guards in the next iteration; again, with or without cutting plane.
, we need to introduce the notion of a polygon corresponding to C k−1 k . This allows us to examine the underlying geometry of α S in the AGP.
We may refer to G(P ) and W (P ) by just G and W , respectively.
Note that in P k−1 k the full circulant C k−1 k completely describes the visibility relations between G and W . This implies that the optimal solution of AGR(G, W ) is 1 k−1 · 1, with cost k k−1 . It is feasible for AGR(G, P k−1 k ) by Property (9), as any point w ∈ P k−1 k is covered by at least (k − 1) · 1 k−1 = 1. Fig. 4 captures construction attempts for models of C k−1 k . P 2 3 exists; however, as we prove in Theorem 2, the polygons for k ≥ 4 are either star-shaped or not full circulant. If they are star-shaped, the optimal solution is to place one guard within the kernel. If they are not full circulant polygons, the optimal solution of AGR(G, W ) is infeasible for AGR(G, P ) and the current fractional solution is intermittent, i.e., cut off in the next iteration. Both cases eliminate the need for a cutting plane, and we may avoid the NP-complete separation problem by restricting separation to k = 3.
In the following we prove that P k−1 k is star-shaped for k ≥ 4. We start with Lemma 3, which shows that any pair of guards in G is sufficient to cover There are k − 1 guards in H 1 and in H 2 , so there must be k − 2 in their intersection. This only leaves 2 guards for H 3 .  In order for w 1 to fulfill (9), at least k−1 of the guards in G must be located in V(w 1 ) ⊆ H 1 . Analogously, there must be k − 1 guards in H 2 . Covering w 1 and w 2 with a total of k guards is only possible if at least k − 2 guards of G are located in the intersection of the two half-spaces: 3 , a possible AG interpretation of C 2 3 with a hole. It proves that the bound of k ≥ 4 in Lemma 4 is tight.
As shown in Fig. 6, k ≥ 4 is tight: a triangle with a concentric triangular hole is an example of P 2 3 , with guards in the outside corners and witnesses on the inside edges.
We require one final lemma before proceeding to the main Theorem 2.
Proof. n + m ≤ 2 is trivial, so consider n + m ≥ 3. Because of P 1 ∩ P 2 = i=1,...,n+m H i = ∅, Helly's Theorem applied to the the two-dimensional convex half-spaces H i implies the existence of three half-spaces H i , H j , and H k , i < j < k, with H i ∩ H j ∩ H k = ∅. W. l. o. g., we assume i = 1, j = 2 and k = n + 1, which provides so it follows that P 1 ∩ H n+1 = ∅ with P 2 ⊆ H n+1 by construction, and H n+1 is the half-space whose existence is the claim. Now all preliminaries for the main theorem of the section are met and we can proceed to Theorem 2, which claims that full circulant polygons are star-shaped for k ≥ 4.
Proof. Refer to Fig. 7. Let P k−1 k with k ≥ 4 be a full circulant polygon. The guards in G = G P k−1 k must be covered by a total of k − 1 guards, i. e., they must also fulfill (9), so each guard can see at least k − 2 others. W. l. o. g., let g 1 and g 2 denote two guards in each other's field of view.
with guards g 1 and g 2 . P 1 and P 2 are the gray areas at the top. P 1 is seen by g 1 but not by g 2 ; an analogous property holds for P 2 . The rest of P k−1 k is P 12 , a star entirely seen by both g 1 and g 2 , K is its kernel. L is the area whose view into P 1 ∪ P 2 is not blocked by any edge of P k−1 k that coincides with P 1 ∪ P 2 . It contains all of g 3 , . . . , g k . If P would be added to P k−1 k , K would be cut off below the dashed line containing w and K ∩ L = ∅. But then no point in L, including g 3 , . . . , g k , could see w , a contradiction to the property of P k−1 k requiring k − 1 guards to see any of its points.

Now consider
, the subset of P k−1 k seen by both g 1 and g 2 . It is star-shaped, because g 1 and g 2 are in its kernel, which we denote by K. The rest of P k−1 k , i. e., P k−1 k \ P 12 , consists of two types of areas: 1. P 1 = P k−1 k \ (P 12 ∪ V(g 2 )), points visible from g 1 , but not from g 2 . 2. P 2 = P k−1 k \ (P 12 ∪ V(g 1 )), points visible from g 2 , but not from g 1 .
There exists no w ∈ P k−1 k seen by neither g 1 nor g 2 , because P k−1 k = V(g 1 ) ∪ V(g 2 ), due to Lemma 3. Thus, P k−1 k = P 12∪ P 1∪ P 2 . We now examine which guards can see what part of P 12 , P 1 and P 2 . For that, we classify three types of edges. Gray edges are those edges of P k−1 k that coincide with P 1 or P 2 , white edges denote the other edges of P k−1 k . Finally, edges of P 12 not part of P k−1 k that separate P 1 ∪ P 2 from P 12 are referred to as white-gray edges. Note that white-gray edges do not block the view of any guard in P k−1 k , because they are merely edges of the auxiliary polygon P 12 . K is the intersection of all half-spaces induced by white or white-gray edges, because a star's kernel is the intersection of all half-spaces induced by its edges.
We provide an estimate for the points that are able to cover all of P 1 ∪ P 2 . These points must be contained in L = g ∈ R 2 | no gray edge blocks g's view into P 1 or P 2 = e is gray edge Half-space induced by e.
Some points in L may be located outside of P k−1 k , and even those points of L inside of P k−1 k may not be able to see all of P 1 ∪ P 2 , due to white edges blocking their view.ḡ in Fig. 7 is an example for this case: it cannot see the rightmost part of P 2 . However, L = ∅, because g 3 , . . . , g k ∈ L ∩ P k−1 k . Every g i ∈ G with 3 ≤ i ≤ k is able to see all of P 1 ∪ P 2 : g i can see all of P 1 , because g 2 , g i are a 2-cover of P k−1 k ; g i can entirely see P 2 , because g 1 , g i are also a 2-cover by Lemma 3.
The remaining part of the proof involves two steps. First, we argue that any point in K ∩ L can see all of P k−1 k ; then we show that K ∩ L = ∅, i. e., that P k−1 k is star-shaped. For the first step, assume there exists some g ∈ K ∩ L. Now g has the following properties: g can see all of P 12 by definition of K, which includes the interior of P 12 , all white and all white-gray edges. 3. Because P k−1 k has no holes by Lemma 4, g's view on the white-gray edges is not blocked; and due to g ∈ L, there is nothing left that can block g's view into P 1 ∪ P 2 .
So g ∈ kernel P k−1 k , provided that K ∩ L = ∅; we show the latter in the final step: K and L are two-dimensional polyhedra, each of their edges is a facet. Suppose their intersection is empty; then by Lemma 5, there must be a facet of one of them that separates them from each other. We consider three cases, because K has two types of edges and L has one: 1. The facet is a facet of K, induced by a white edge e. Now consider a point w in the interior of e. w is seen by g 1 and g 2 , but not by any of the points g 3 , . . . , g k , because g 3 , . . . , g k ∈ L, and e induces a facet separating K from L. Due to k ≥ 4, this makes |V(w) ∩ G| ≥ k − 1, i. e., (9), impossible and thus contradicts the requirement of P k−1 k being a full circulant polygon. This would be the case in Fig. 7, if P k−1 k had the extension P , which would cut off the lower part of K and thus separate K from L. However, then only g 1 and g 2 but none of g 3 , . . . , g k could see w , which violates (9). 2. The facet is a facet of K, induced by a white-gray edge e. As e is a whitegray edge, there is a part of P 1 or P 2 adjacent to e. This part cannot be seen from any point in L, because the facet induced by e is a facet of K and separates K from L by assumption, and because P k−1 k has no holes by Lemma 4. However, g 3 , . . . , g k ∈ L not being able to see P 1 or P 2 contradicts (9).
3. The facet is a facet of L. This means that there is some gray edge e corresponding to that facet. A point w in e's interior is not seen by g 1 or g 2 , because the facet separates K from L. So s is not seen by more than k − 2 guards, and thus violates (9).
All cases lead to contradictions, and thus K ∩ L = ∅. Therefore, P k−1 k has a non-empty kernel, and is star-shaped for k ≥ 4, as claimed.
Theorem 2 does not rule out situations in which P k−1 k , for k ≥ 4 is part of a larger polygon, as shown in Fig. 8. This example has no integrality gap; placing at least five copies of P 3 4 around an appropriate central subpolygon with a hole can actually create one. However, such cases are much harder to come by, making the k ≥ 4 facets a lot less useful for cutting off fractional solutions.
Theorem 2 does, however, provide a very useful separation heuristic. As the separation problem is NP-complete for unlimited k, but solvable in polynomial time for a fixed k, it is clear that k must be limited in a practical algorithm. Theorem 2 justifies restricting k = 3 from a theoretical point of view, by stating that the underlying geometry for k > 3 is star-shaped, i. e., allows placing one non-fractional guard in its kernel, see Fig. 4. As we show in Section 6, this can also be validated in an experimental setting.

All Art Gallery Facets with Coefficients {0, 1, 2}
For finite G, W ⊂ P , AGP(G, W ) is also an SC instance. Balas and Ng identified all SC facets with coefficients in {0, 1, 2} [3]; so we present all AGP facets with coefficients {0, 1, 2}. This includes three trivial facet classes, (13) - (15), which are unable to cut off fractional solutions of AGR(G, W ). The only non-trivial facet in this inventory is the one of type α S described above.
is a facet of a full-dimensional conv(AGP(G, W )), iff |V(w) ∩ G \ {g}| ≥ 2 for all w ∈ W , i. e., if every witness sees at least two guards other than g. is feasible and optimal, even though no guard is placed in any of the P 3 4 kernels.
A second type of AGP facet is the upper bound of one for every guard value. It is a facet of every full-dimensional conv(AGP(G, W )) [3]: The third and last trivial AGP facet with coefficients in {0, 1, 2} is This simply is the constraint induced by the witness w ∈ W , which enforces sufficient coverage of w. It is facet defining iff two conditions hold: First, there must not be any witness w ∈ W with V(w ) ∩ G ⊂ V(w) ∩ G. Otherwise, the coverage of w would be implied by that of w . Second, for any guard g ∈ G \ V(w), there exists some other guard g ∈ V(w) ∩ G that can see all of [3]. The fourth, and the only non-trivial, AGP facet with coefficients in {0, 1, 2} is the facet of type α S , which is thoroughly analyzed above.

Edge Cover Facets
Solving AGR(G, W ) for finite G, W ⊂ P , such that no guard can see more than two witnesses is equivalent to solving fractional edge cover (EC) on the graph with nodes W , an edge between v = w ∈ W for each g ∈ G with V(g) ∩ W = {v, w}, and a loop for each g ∈ G with V(g) ∩ W = {w}. The fractional EC polytope is known to be half-integral [16], which can be exploited to show that fractional solutions always form odd-length cycles of 1 2 -guards. In the conclusions of [13], we proposed a class of valid inequalities motivated by this. The idea is to identify k witnesses W = {w 1 , . . . , w k }, such that no point exists that can see more than two of them. Then at least k 2 binary guards are needed for covering W . Two examples are shown in Figure 9.
Obviously, for any choice of P ⊇ G ⊃ G, (16) does not cut off any feasible solution x ∈ {0, 1} G of AGP(G , P ), as long as no point in P exists that sees more than two of these witnesses. So, analogously to the SC cuts, a cut can be represented as visiblity overlay α W and kept in future iterations once it has been identified.
It is not hard to show that these are facet defining under relatively mild conditions. Theorem 3 Let P be a polygon with finite sets of guard and witness positions G, W ⊂ P , such that conv(AGP(G, W )) is full-dimensional. Let W = {w 1 , . . . , w k } ⊆ W be an odd subset of k ≥ 3 witnesses, such that Figure 9 Two situations, in which no guard exists that can see more than two witnesses. On the left, assigning g 1 = · · · = g 5 = 1 2 results in an optimal fractional solution of 5 2 , compare [13]. Applying (16) yields g 1 + · · · + g 5 ≥ 5+1 2 = 3 and cuts off this fractional solution. On the right, the optimal fractional solution is g 1 = g 2 = g 3 = 1 2 . (16) provides the constraint g 1 + g 2 + g 3 ≥ 3+1 2 = 2, which cuts off that fractional solution as well.
1. No guard sees more than two witnesses in W .
2. If a guard sees two witnesses w i = w j ∈ W , they are a successive pair, i. e., i + 1 = j or i = 1 and j = k. 3. Each of the k successive pairs is seen by some g ∈ G. 4. No guard inside of V W sees a witness outside of W .
Then the constraint is a facet of conv(AGP(G, W )).
Proof. As no guard sees more than two witnesses of W , it is clear that it takes at least k 2 guards to cover W . It remains to be shown how to construct n = |G| affinely independent solutions of AGP(G, W ). In order to do that, we separate the guards into three groups G 1∪ G 2∪ G 3 = G with |G i | = n i : 1. G 1 is a set of one guard for each successive pair as in Condition 3. 2. G 2 contains all guards in V W that are not already part of G 1 : 3. G 3 holds the rest of the guards, which are outside of V(W ): In the following, we describe a solution x ∈ {0, 1} G by x = (x G1 , x G2 , x G3 ), where x Gi ∈ {0, 1} Gi denotes the vector (x g1 , . . . , x gn i ) with G i = {g 1 , . . . , g ni }.
x n1 = ((0, 1, 0, 1, . . . , 0, 1, 1), 0, 1) , which exists because of Condition 3 and the choice of G 1 . It fulfills (17) with equality because it uses k 2 guards, and it is feasible, because W and W \ W are covered by construction and due to guards not in G 3 not interfering with the coverage of witnesses in W \ W .
The second set provides n 2 solutions by using the i-th unit vector as x G2 .
As every successive pair of witnesses is covered by some guard in G 1 , a choice of x such that x i fulfills (17) with equality is always possible. The third and last set of n 3 solutions is constructed by subtracting e i from 1 in the vector x G3 : 0, 1, 0, . . . , 1, 0, 1 It fulfills (17) with equality. Setting one guard value to zero in G 3 is feasible because in a full-dimensional conv(AGP(G, W )), every witness is seen by at least two guards, compare Lemma 1. All in all, we have n 1 + n 2 + n 3 = n feasible, affinely independent solutions of AGP(G, W ) fulfilling (17) with equality, so (17) has dimension n − 1 and is a facet, as claimed.

Computational Experience
A variety of experiments on benchmark polygons demonstrates the usefulness of our cutting planes, as well as the apropriateness of our separation heuristic of using only k = 3 for the SC related facets from Section 4.
We test our cutting planes in two variations of our algorithm, IP and LP mode. Both test cases have a lot in common, as described in the following. For mode-specific results refer to the dedicated Sections 6.1 and 6.2.
Just as in [13], we employed four different classes of benchmark polygons.  3. Random non-orthogonal Simple polygons as in Fig. 10, thrid polygon. 4. Random Spike polygons (mostly with holes) as in Fig. 10, fourth polygon.
Each polygon class was evaluated for different sizes n ∈ {60, 200, 500, 1000}, where n is the approximate number of vertices in a polygon.
Different combinations of cut separators were also employed. The ECrelated cuts from Section 5 are referred to as EC cuts, while the SC-related cuts of Section 4 that rely on separating a maximum of 3 ≤ k witnesses are denoted by SCk cuts. Note that for 3 ≤ m ≤ k, SCk cuts also include all SCm cuts.
Whenever the above algorithm separates cuts, it applies all configured cut separators and we test the following combinations: no cut separation at all, SC3 cuts only, SC4 cuts only, EC cuts only, and SC3 and EC cuts at the same time.
In total, we have two modes, five combinations of separators, four classes of polygons, and four polygon sizes; for each combination, we tested 10 different polygons. The experiments were run on 3.0 GHz Intel dual core PCs with 2 GB of memory, running 32 bit Debian 6.0.5 with Linux 2.6.32-686. Our algorithms were not parallelized, used version 4.0 of the "Computational Geometry Algorithms Library" (CGAL) and CPLEX 12.1. Each test run had a time limit of 600 s.

IP Mode
The test algorithm in IP mode is a variation of the one introduced in [13], which always determines binary solutions at the expense of not necessarily terminating due to the integrality gap.
The sets G and W are initialized with the vertices of P , while A = ∅. In the primal phase, we solve AGP(G, W, A). Should the solution be feasible for AGP(G, P, A), we have identified an upper bound. Otherwise, there are witnesses W ⊂ P \ W whose constraints are violated. In this case, W is augmented with some of the insufficiently covered witnesses and the primal phase is continued. When an upper bound is found, the dual phase is entered. A lower bound is generated by iteratively solving the dual of AGR(G, W, A). If the solution is feasible for the dual of AGR(P, W, A) and the cut separators do not find a violated constraint either, we have a lower bound. Otherwise, guards with violated dual constraints are added to G, violated cut conditions are added to A, and the dual phase continues until a lower bound is found. Then the algorithm continues with a primal phase, etc. This process is repeated until the upper and the lower bound meet, or a timeout occurs.
In Figure 11 we present the relative gap over time for the five tested cut separator selections for the von Koch-type polygons with 1000 vertices. Fig. 11(a) shows the relative gap over time without cut separation. After about 400 s, gaps are fixed between 0% and 6%, the median gap being 2%. When applying the EC separator ( Fig. 11(b)), 75% of the gaps drop to zero and the largest gap is 2%. Using the SC3 separator (Fig. 11(c)) yields an even better result in terms of both speed and relative gap. All gaps are closed, many of them earlier than with the EC separator. Combining both, see Fig. 11(d), yields a result comparable to using only SC3. Moving to the SC4 separator (Fig. 11(e)) yields a weaker performance: computation times go up, and not all gaps reach 0% within the allotted time, because separation takes longer without improving the gap. This illustrates the practical consequences of Theorem 2. We briefly iterate through the remaining testcases. For the Orthogonal -type polygons with 1000 vertices in Figure 12, EC and SC3 separation yield an improvement over using no separation: The maximum relative gap drops and some gaps reach their 600 s levels earlier. Joint application of SC3 and EC provides the best results. SC4 and SC3 separation only differ in the extreme cases of the minimum and the maximum relative gap.
The 1000-vertex Simple polygons, see Figure 13, allow a slight improvement of the relative gap with EC as well as SC3 separation; joint application yields the best results. A difference to the other experiments is that the SC4 separator performs slightly better than the SC3 separator -an isolated observation.
Our separators have no measurable impact on the Spike-type polygons, see Figure 14. Larger instances of this type of polygon take much time when solving the first couple of IPs, which means our separators are triggered late in the 600 s time limit -or not at all.

LP Mode
Analogously to the IP mode, we test the separators in a slightly different setting referred to as LP mode. It works like the algorithm described in Section 6.1, but with the following difference: In the primal phase, it solves the LP AGR(G, W, A) instead of the IP. If a solution of AGR(G, W, A) is feasible for AGR(G, P, A) and if it happens to be binary, it is considered an upper bound, otherwise it is discarded and the primal phase is continued. In addition, cut separation is performed in each step of the primal as well as in the dual phase. The challenge of the LP mode is to find a binary solution at all, because the algorithm might stick to fractional optimal solutions that are not handled For the von Koch polygons in Figure 15, the EC separator provides a slight improvement, the SC3 separator a stronger improvement; the best result is obtained when using both of them. SC4 separation is weaker than SC3 separation.
The EC separator does not improve the situation for the Orthogonal polygons, Fig. 16, but the SC3 separator boosts solution percentage beyond 75%. Joint application of both separators results in even smaller gaps. SC4 cut separation yields mixed results: The median relative gap is larger, while the Q 3 gap is smaller but takes approximately 350 s longer to reach its value. In addition, the Q 1 curve takes much longer to drop to zero as well.
The situation for the Simple polygons in Figure 17 is as follows. EC separation has no impact on the results, when applied alone as well as when used jointly. As above, SC3 separation is better than SC4 separation, it solves more instances.
EC cuts have no impact on the Spike polygons, Fig. 18, but SC3 helps solving all of them instead of less than 25%. In this case, the SC4 separator is approximately 10 s faster in the Q 1 , Q 2 and Q 3 quartiles and 30 s for the maximum.
We present Table 1 that summarizes the solution percentage after 600 s in LP mode as well as the median relative gap.

Conclusion
In this paper, we have shown how we can exploit both geometric properties and polyhedral methods of mathematical programming to solve a classical and natural, but highly challenging problem from computational geometry.
We have shown how to integrate cutting planes into linear programming formulations of the Art Gallery Problem (AGP), a linear program with a potentially infinite number of both variables and constraints. Additionally, we provided three trivial and two non-trivial facets of the AGP polytope, including a complete list of all AGP facets with coefficients in {0, 1, 2}.
Furthermore, we have exploited the underlying geometric properties of the AGP to identify a subset of one of our facet classes, that 1. can be separated in polynomial time, although the general separation problem is NP-complete. 2. is theoretically justified by showing that geometry behind the cutting planes is star-shaped for the cases excluded in separation. 3. is justified by experimental data.
This promises to pave the way for a range of practical AGP applications that have to deal with additional real-life aspects. We are optimistic that our basic approach can also be used for other geometric optimization problems.