polygon, the color with the fewest vertices defines a valid guard set with at most guards. Illustration of the proof To illustrate the proof, we consider the polygon below. The first step is to triangulate the polygon (see Figure 1). Then, one applies a proper -colouring (Figure 2) and observes that there are red, blue and green vertices. The colour with the fewest vertices is blue or red, thus the polygon can be covered by guards (Figure 3). This agrees with the art gallery theorem, because the polygon has vertices, and . Generalizations Chvátal's upper bound remains valid if the restriction to guards at corners is loosened to guards at any point not exterior to the polygon. There are a number of other generalizations and specializations of the original art-gallery theorem. For instance, for orthogonal polygons, those whose edges/walls meet at right angles, only guards are needed. There are at least three distinct proofs of this result, none of them simple: by Kahn, Klawe, and Kleitman; by Lubiw; and by Sack and Toussaint. A related problem asks for the number of guards to cover the exterior of an arbitrary polygon (the "Fortress Problem"): are sometimes necessary and always sufficient if guards are placed on the boundary of the polygon, while are sometimes necessary and always sufficient if guards are placed anywhere in the exterior of the polygon. In other words, the infinite exterior is more challenging to cover than the finite interior. Computational complexity In decision problem versions of the art gallery problem, one is given as input both a polygon and a number k, and must determine whether the polygon can be guarded with k or fewer guards. This problem is -complete, as is the version where the guards are restricted to the edges of the polygon. Furthermore, most of the other standard variations (such as restricting the guard locations to vertices) are NP-hard. Regarding approximation algorithms for the minimum number of guards, proved the problem to be APX-hard, implying that it is unlikely that any approximation ratio better than some fixed constant can be achieved by a polynomial time approximation algorithm. showed that a logarithmic approximation may be achieved for the minimum number of vertex guards by discretizing the input polygon into convex subregions and then reducing the problem to a set cover problem. As showed, the set system derived from an art gallery problem has bounded VC