Editing Art gallery problem (section)

==Two dimensions==
[[File:Art gallery problem.svg|thumb|Four guards are able to cover this gallery.]]
There are numerous variations of the original problem that are also referred to as the art gallery problem.  In some versions guards are restricted to the perimeter, or even to the vertices of the polygon.  Some versions require only the perimeter or a subset of the perimeter to be guarded.

Solving the version in which guards must be placed on vertices and only vertices need to be guarded is equivalent to solving the [[dominating set problem]] on the [[visibility graph]] of the polygon.

===Chvátal's art gallery theorem===
Chvátal's art gallery theorem, named after [[Václav Chvátal]], gives an [[upper bound]] on the minimal number of guards. It states:

<blockquote> "To guard a simple polygon with <math>n</math> vertices, <math>\left\lfloor n/3 \right\rfloor</math> guards are always sufficient and sometimes necessary." </blockquote>

=== History ===
The question about how many vertices/watchmen/guards were needed, was posed to Chvátal by [[Victor Klee]] in 1973.{{sfnp|O'Rourke|1987|p=1}} Chvátal proved it shortly thereafter.{{sfnp|Chvátal|1975}} Chvátal's proof was later simplified by Steve Fisk, via a [[graph coloring|3-coloring]] argument.{{sfnp|Fisk|1978}} Chvátal has a more geometrical approach, whereas Fisk uses well-known results from [[Graph theory]].

=== Fisk's short proof ===
[[File:Triangulation 3-coloring.svg|thumb|A 3-coloring of the vertices of a triangulated polygon. The blue vertices form a set of three guards, as few as is guaranteed by the art gallery theorem. However, this set is not optimal: the same polygon can be guarded by only two guards.]]
Steve Fisk's proof is so short and elegant that it was chosen for inclusion in ''[[Proofs from THE BOOK]]''.{{sfnp|Aigner|Ziegler|2018}}
The proof goes as follows:

First, the polygon is [[Polygon triangulation|triangulated]] (without adding extra vertices), which is possible, because the existence of triangulations is proven under certain verified conditions. The vertices of the resulting triangulation graph may be [[Graph coloring|3-colored]].{{efn|To prove 3-colorability of polygon triangulations, we observe that the weak [[dual graph]] to the triangulation (the [[undirected graph]] having one vertex per triangle and one edge per pair of adjacent triangles) is a [[Tree (graph theory)|tree]], since any cycle in the dual graph would form the boundary of a hole in the polygon, contrary to the assumption that it has no holes. Whenever there is more than one triangle, the dual graph (like any tree) must have a vertex with only one neighbor, corresponding to a triangle that is adjacent to other triangles along only one of its sides. The smaller polygon formed by removing this triangle has a 3-coloring by [[mathematical induction]], and this coloring is easily extended to the one additional vertex of the removed triangle.{{sfnp|O'Rourke|1987|p=13}}}} Clearly, under a 3-coloring, every triangle must have all three colors. The vertices with any one color form a valid guard set, because every triangle of the polygon is guarded by its vertex with that color. Since the three colors partition the ''n'' vertices of the polygon, the color with the fewest vertices defines a valid guard set with at most <math>\lfloor n/3\rfloor</math> 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 <math>3</math>-colouring (''Figure 2'') and observes that there are <math>4</math> red, <math>4</math> blue and <math>6</math> green vertices. The colour with the fewest vertices is blue or red, thus the polygon can be covered by <math>4</math> guards (''Figure 3''). This agrees with the art gallery theorem, because the polygon has <math>14</math> vertices, and <math>\left\lfloor \frac{14}{3} \right\rfloor = 4</math>.
<gallery mode="nolines" class="center">
File:Triangulation of polygon.png|Figure 1
File:3-coloring of the polygon.png|Figure 2
File:Least color of 3-coloration.png|Figure 3
</gallery>

===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.<ref>{{harvtxt|Shermer|1992}}; {{harvtxt|Urrutia|2000}}</ref> For instance, for [[orthogonal polygons]], those whose edges/walls meet at right angles, only <math>\lfloor n/4 \rfloor</math> guards are needed. There are at least three distinct proofs of this result, none of them simple: by Kahn, [[Maria Klawe|Klawe]], and [[Daniel Kleitman|Kleitman]]; by [[Anna Lubiw|Lubiw]]; and by [[Jörg-Rüdiger Sack|Sack]] and [[Godfried Toussaint|Toussaint]].<ref>{{harvtxt|Kahn|Klawe|Kleitman|1983}}; {{harvtxt|Lubiw|1985}}; {{harvtxt|Sack|Toussaint|1988}}.</ref>{{sfnp|O'Rourke|1987|pp=31–80}}

A related problem asks for the number of guards to cover the exterior of an arbitrary polygon (the "Fortress Problem"): <math>\lceil n/2 \rceil</math> are sometimes necessary and always sufficient if guards are placed on the boundary of the polygon, while <math>\lceil n/3 \rceil</math> are sometimes necessary and always sufficient if guards are placed anywhere in the exterior of the polygon.{{sfnp|O'Rourke|1987|pp=146–154}} 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 [[Existential theory of the reals|<math>\exists\mathbb{R}</math>-complete]], as is the version where the guards are restricted to the edges of the polygon.{{sfnp|Abrahamsen|Adamaszek|Miltzow|2022}} Furthermore, most of the other standard variations (such as restricting the guard locations to vertices) are [[NP-hard]].<ref>{{harvtxt|O'Rourke|Supowit|1983}}; {{harvtxt|Lee|Lin|1986}}.</ref>
 
Regarding [[approximation algorithm]]s for the minimum number of guards, {{harvtxt|Eidenbenz|Stamm|Widmayer|2001}} 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]]. {{harvtxt|Ghosh|1987}} showed that a [[logarithm]]ic 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 {{harvtxt|Valtr|1998}} showed, the set system derived from an art gallery problem has bounded [[VC dimension]], allowing the application of set cover algorithms based on [[ε-net (computational geometry)|ε-nets]] whose approximation ratio is the logarithm of the optimal number of guards rather than of the number of polygon vertices.{{sfnp|Brönnimann|Goodrich|1995}} For unrestricted guards, the infinite number of potential guard positions makes the problem even more difficult. 
However by restricting the guards to lie on a fine grid, a more complicated [[logarithm]]ic approximation algorithm can be derived under some mild extra assumptions, as shown by {{harvtxt|Bonnet|Miltzow|2017}}. However, efficient algorithms are known for finding a set of  at most <math>\left\lfloor n/3 \right\rfloor</math> vertex guards, matching Chvátal's upper bound.
{{harvs|first1=David|last1=Avis|author1-link=David Avis|first2=Godfried|last2=Toussaint|author2-link=Godfried Toussaint|year=1981|txt}} proved that a placement for these guards may be computed in O(n ''log'' n) time in the worst case, via a [[divide and conquer algorithm]].
{{harvtxt|Kooshesh|Moret|1992}} gave a [[linear time]] algorithm by using Fisk's short proof and [[Bernard Chazelle]]'s linear time plane triangulation algorithm.

For simple polygons that do not contain holes, the existence of a constant factor approximation algorithm for vertex and edge guards was conjectured by Ghosh. Ghosh's conjecture was initially shown to be true for vertex guards in two special sub-classes of simple polygons, viz. monotone polygons and polygons weakly visible from an edge. {{harvtxt|Krohn|Nilsson|2013}} presented an approximation algorithm that computes in polynomial time a vertex guard set for a monotone polygon such that the size of the guard set is at most 30 times the optimal number of vertex guards. {{harvtxt|Bhattacharya|Ghosh|Roy|2017}} presented an approximation algorithm that computes in O(n<sup>2</sup>) time a vertex guard set for a simple polygon that is weakly visible from an edge such that the size of the guard set is at most 6 times the optimal number of vertex guards. Subsequently, {{harvtxt|Bhattacharya|Ghosh|Pal|2017}} claimed to have settled the conjecture completely by presenting constant factor approximation algorithms for guarding general simple polygons using vertex guards and edge guards. For vertex guarding the subclass of simple polygons that are weakly visible from an edge, a [[polynomial-time approximation scheme]] was proposed by {{harvtxt|Ashur|Filtser|Katz|Saban|2019}}.

An exact algorithm was proposed by {{harvtxt|Couto|de  Rezende|de Souza|2011}}  for vertex guards. The authors conducted extensive computational experiments with several classes of polygons showing that optimal solutions can be found in relatively small computation times even for instances associated to thousands of vertices. The input data and the optimal solutions for these instances are available for download.<ref>{{harvtxt|Couto|de Rezende|de Souza|2011}}.</ref>