# Art gallery problem

Last updated

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:

## Contents

"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"

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. A set ${\displaystyle S}$ of points is said to guard a polygon if, for every point ${\displaystyle p}$ in the polygon, there is some ${\displaystyle q\in S}$ such that the line segment between ${\displaystyle p}$ and ${\displaystyle q}$ does not leave 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. Other domains, where this problem is applied, are in image editing, lighting problems of a stage or installation of infrastructures for the warning of natural disasters.

## Two dimensions

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, named after Václav Chvátal, gives an upper bound on the minimal number of guards. It states:

"To guard a simple polygon with ${\displaystyle n}$ vertices, ${\displaystyle \left\lfloor n/3\right\rfloor }$ guards are always sufficient and sometimes necessary."

### History

The question about how many vertices/watchmen/guards were needed, was posed to Chvátal by Victor Klee in 1973. [1] Chvátal proved it shortly thereafter. [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.

### Fisk's short proof

Steve Fisk's proof is so short and elegant that it was chosen for inclusion in Proofs from THE BOOK . [4] The proof goes as follows:

First, the polygon is 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 3-colored. [lower-alpha 1] 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 ${\displaystyle \lfloor n/3\rfloor }$ 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 ${\displaystyle 3}$-colouring (Figure 2) and observes that there are ${\displaystyle 4}$ red, ${\displaystyle 4}$ blue and ${\displaystyle 6}$ green vertices. The colour with the fewest vertices is blue or red, thus the polygon can be covered by ${\displaystyle 4}$ guards (Figure 3). This agrees with the art gallery theorem, because the polygon has ${\displaystyle 14}$ vertices, and ${\displaystyle \left\lfloor {\frac {14}{3}}\right\rfloor =4}$.

### 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. [6] For instance, for orthogonal polygons, those whose edges/walls meet at right angles, only ${\displaystyle \lfloor n/4\rfloor }$ 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. [7] [8]

A related problem asks for the number of guards to cover the exterior of an arbitrary polygon (the "Fortress Problem"): ${\displaystyle \lceil n/2\rceil }$ are sometimes necessary and always sufficient if guards are placed on the boundary of the polygon, while ${\displaystyle \lceil n/3\rceil }$ are sometimes necessary and always sufficient if guards are placed anywhere in the exterior of the polygon. [9] 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 ${\displaystyle \exists \mathbb {R} }$-complete, as is the version where the guards are restricted to the edges of the polygon. [10] Furthermore, most of the other standard variations (such as restricting the guard locations to vertices) are NP-hard. [11]

Regarding approximation algorithms for the minimum number of guards, 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. 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. [12] 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 logarithmic approximation algorithm can be derived under some mild extra assumptions, as shown by Bonnet & Miltzow (2017). However, efficient algorithms are known for finding a set of at most ${\displaystyle \left\lfloor n/3\right\rfloor }$ vertex guards, matching Chvátal's upper bound. DavidAvis 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. monotone polygons and polygons weakly visible from an edge. 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. Subsequently, 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 Ashur et al. (2019).

An exact algorithm was proposed by 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. [13]

## Three dimensions

If a museum is represented in three dimensions as a polyhedron, then putting a guard at each vertex will not ensure that all of the museum is under observation. Although all of the surface of the polyhedron would be surveyed, for some polyhedra there are points in the interior which might not be under surveillance. [15]

Possible Usage Scenarios of the Art Gallery Problem

The art gallery problem can be used to position multiple cameras when the objective is to cover a large area in view of cameras, using the minimum number of cameras.

## Notes

1. 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, 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. [5]

## Related Research Articles

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.

In computational geometry, polygon triangulation is the partition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

In geometry an arrangement of lines is the subdivision of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. In more colloquial terms, in a party of people some of whom shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler (1736) in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.

In graph theory, the crossing numbercr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.

In the mathematical field of graph theory, the friendship graphFn is a planar, undirected graph with 2n + 1 vertices and 3n edges.

In graph theory, the graph bandwidth problem is to label the n vertices vi of a graph G with distinct integers so that the quantity is minimized . The problem may be visualized as placing the vertices of a graph at distinct integer points along the x-axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement.

In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of as an intersection graph of finite sets. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of cliques needed to cover all of the edges of .

In geometry, a covering of a polygon is a set of primitive units whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

In geometry, the two ears theorem states that every simple polygon with more than three vertices has at least two ears, vertices that can be removed from the polygon without introducing any crossings. The two ears theorem is equivalent to the existence of polygon triangulations. It is frequently attributed to Gary H. Meisters, but was proved earlier by Max Dehn.

In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.

In computational geometry, a fan triangulation is a simple way to triangulate a polygon by choosing a vertex and drawing edges to all of the other vertices of the polygon. Not every polygon can be triangulated this way, so this method is usually only used for convex polygons.

Art Gallery Theorems and Algorithms is a mathematical monograph on topics related to the art gallery problem, on finding positions for guards within a polygonal museum floorplan so that all points of the museum are visible to at least one guard, and on related problems in computational geometry concerning polygons. It was written by Joseph O'Rourke, and published in 1987 in the International Series of Monographs on Computer Science of the Oxford University Press. Only 1000 copies were produced before the book went out of print, so to keep this material accessible O'Rourke has made a pdf version of the book available online.

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

## References

1. O'Rourke (1987), p. 1.
2. O'Rourke (1987), p. 13.
3. O'Rourke (1987), pp. 31–80.
4. O'Rourke (1987), pp. 146–154.
5. Eryk Lipka, A note on minimal art galleries , 2019
6. O'Rourke (1987), p. 255.

## Sources

• Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann (2018), "The art gallery problem is ${\displaystyle \exists \mathbb {R} }$-complete", in Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.), Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25–29, 2018, ACM, pp. 65–73, arXiv:, doi:10.1145/3188745.3188868, MR   3826234, S2CID   15909121
• Aggarwal, A. (1984), The art gallery theorem: Its variations, applications, and algorithmic aspects, Ph.D. thesis, Johns Hopkins University.
• Aigner, Martin; Ziegler, Günter M. (2018), "Chapter 40: How to guard a museum", Proofs from THE BOOK (6th ed.), Berlin: Springer, pp. 281–283, doi:10.1007/978-3-662-57265-8, ISBN   978-3-662-57264-1, MR   3823190 .
• Ashur, Stav; Filtser, Omrit; Katz, Matthew J.; Saban, Rachel (2019), "Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains", in Bampis, Evripidis; Megow, Nicole (eds.), Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12–13, 2019, Revised Selected Papers, Lecture Notes in Computer Science, vol. 11926, Berlin: Springer, pp. 1–17, doi:10.1007/978-3-030-39479-0_1, S2CID   210936577 .
• Avis, D.; Toussaint, G. T. (1981), "An efficient algorithm for decomposing a polygon into star-shaped polygons" (PDF), Pattern Recognition, 13 (6): 395–398, Bibcode:1981PatRe..13..395A, doi:10.1016/0031-3203(81)90002-9 .
• Bhattacharya, Pritam; Ghosh, Subir Kumar; Pal, Sudebkumar (2017), Constant Approximation Algorithms for Guarding Simple Polygons using Vertex Guards, arXiv:
• Bhattacharya, Pritam; Ghosh, Subir Kumar; Roy, Bodhayan (2017), "Approximability of guarding weak visibility polygons", Discrete Applied Mathematics, 228: 109–129, arXiv:, doi:10.1016/j.dam.2016.12.015, MR   3662965, S2CID   9916523
• Bonnet, Édouard; Miltzow, Tillmann (2017), "An approximation algorithm for the art gallery problem", in Aronov, Boris; Katz, Matthew J. (eds.), 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, LIPIcs, vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 20:1–20:15, arXiv:, doi:10.4230/LIPIcs.SoCG.2017.20, MR   3685692, S2CID   1293138 .
• Brönnimann, H.; Goodrich, M. T. (1995), "Almost optimal set covers in finite VC-dimension", Discrete and Computational Geometry, 14 (1): 463–479, doi:.
• Chvátal, V. (1975), "A combinatorial theorem in plane geometry", Journal of Combinatorial Theory, Series B, 18: 39–41, doi:.
• Couto, M.; de Rezende, P.; de Souza, C. (2011), "An exact algorithm for minimizing vertex guards on art galleries", International Transactions in Operational Research, 18 (4): 425–448, doi:10.1111/j.1475-3995.2011.00804.x .
• de Rezende, P.; de Souza, C.; Couto, M.; Tozoni, D. (2011), "The Art Gallery Problem with Vertex Guards", Art Gallery Problem Project, Instituto de Computação.
• Deshpande, Ajay; Kim, Taejung; Demaine, Erik D.; Sarma, Sanjay E. (2007), "A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems", Proc. Worksh. Algorithms and Data Structures , Lecture Notes in Computer Science, vol. 4619, Springer-Verlag, pp. 163–174, doi:10.1007/978-3-540-73951-7_15, hdl:, ISBN   978-3-540-73948-7 .
• Eidenbenz, S.; Stamm, C.; Widmayer, P. (2001), "Inapproximability results for guarding polygons and terrains" (PDF), Algorithmica, 31 (1): 79–113, doi:10.1007/s00453-001-0040-8, S2CID   14532511, archived from the original (PDF) on 2003-06-24.
• Fisk, S. (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:.
• Ghosh, S. K. (1987), "Approximation algorithms for art gallery problems", Proc. Canadian Information Processing Society Congress, pp. 429–434.
• Kahn, J.; Klawe, M.; Kleitman, D. (1983), "Traditional galleries require fewer watchmen", SIAM J. Algebr. Discrete Methods, 4 (2): 194–206, doi:10.1137/0604020 .
• Kooshesh, A. A.; Moret, B. M. E. (1992), "Three-coloring the vertices of a triangulated simple polygon", Pattern Recognition, 25 (4): 443, Bibcode:1992PatRe..25..443K, doi:10.1016/0031-3203(92)90093-X .
• Krohn, Erik A.; Nilsson, Bengt J. (2013), "Approximate guarding of monotone and rectilinear polygons", Algorithmica, 66 (3): 564–594, doi:10.1007/s00453-012-9653-3, hdl:, MR   3044626, S2CID   1458082 .
• Lee, D. T.; Lin, A. K. (1986), "Computational complexity of art gallery problems", IEEE Transactions on Information Theory, 32 (2): 276–282, doi:10.1109/TIT.1986.1057165 .
• Lubiw, A. (1985), "Decomposing polygonal regions into convex quadrilaterals", Proc. 1st ACM Symposium on Computational Geometry, pp. 97–106, doi:10.1145/323233.323247, ISBN   0-89791-163-6, S2CID   15752916 .
• O'Rourke, Joseph (1987), Art Gallery Theorems and Algorithms, Oxford University Press, ISBN   0-19-503965-3 .
• O'Rourke, Joseph; Supowit, Kenneth J. (1983), "Some NP-hard polygon decomposition problems", IEEE Transactions on Information Theory, 29 (2): 181–190, doi:10.1109/TIT.1983.1056648, MR   0712374 .
• Sack, J. R.; Toussaint, G. T. (1988), "Guard placement in rectilinear polygons", in Toussaint, G. T. (ed.), Computational Morphology, North-Holland, pp. 153–176.
• Shermer, Thomas (1992), "Recent Results in Art Galleries" (PDF), Proceedings of the IEEE, 80 (9): 1384–1399, doi:10.1109/5.163407 .
• Urrutia, Jorge (2000), "Art gallery and illumination problems", in Sack, J. -R.; Urrutia, Jorge (eds.), Handbook of Computational Geometry, North-Holland, pp. 973–1027, doi:10.1016/B978-044482537-7/50023-1 .
• Valtr, P. (1998), "Guarding galleries where no point sees a small area", Israel Journal of Mathematics , 104 (1): 1–16, doi:.