Art gallery problem

In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon.

The art gallery problem can be applied in several domains such as in robotics, when artificial intelligences (AI) need to execute movements depending on their surroundings.

In some versions guards are restricted to the perimeter, or even to the vertices of the polygon.

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.

The question about how many vertices/watchmen/guards were needed, was posed to Chvátal by Victor Klee in 1973.

[2] Chvátal's proof was later simplified by Steve Fisk, via a 3-coloring argument.

[3] Chvátal has a more geometrical approach, whereas Fisk uses well-known results from Graph theory.

The colour with the fewest vertices is blue or red, thus the polygon can be covered by

There are a number of other generalizations and specializations of the original art-gallery theorem.

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.

[9] In other words, the infinite exterior is more challenging to cover than the finite interior.

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.

[10] Furthermore, most of the other standard variations (such as restricting the guard locations to vertices) are NP-hard.

Ghosh (1987) 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 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 ε-nets whose approximation ratio is the logarithm of the optimal number of guards rather than of the number of polygon vertices.

However by restricting the guards to lie on a fine grid, a more complicated logarithmic approximation algorithm can be derived under some mild extra assumptions, as shown by Bonnet & Miltzow (2017).

vertex guards, matching Chvátal's upper bound.

David Avis and Godfried Toussaint (1981) 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.

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.

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.

Bhattacharya, Ghosh & Roy (2017) presented an approximation algorithm that computes in O(n2) 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.

For vertex guarding the subclass of simple polygons that are weakly visible from an edge, a polynomial-time approximation scheme was proposed by Ashur et al. (2019).

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.

Although all of the surface of the polyhedron would be surveyed, for some polyhedra there are points in the interior that might not be under surveillance.