The art gallery problem or museum problem is a well-studied in computational geometry . The task arises in the real world as the task of protecting an art gallery with a minimum number of guards who are able to see the entire gallery. In the version of the task for computational geometry, the gallery is represented as a simple polygon , and each guard is represented as a point inside the polygon. They say a lot of points protects the polygon if for any point such a point exists inside the polygon that the segment connecting and lies completely inside the polygon.
Content
Two-dimensional space
There are many variations of the original problem, and all of them are called the gallery problem. In some cases, guards must be around the perimeter or, even, at the vertices of the polygon. In some embodiments, protection of only the perimeter or part of the perimeter is required.
The solution to the variant in which the guard should be placed only at the vertices and only the vertices should be guarded is equivalent to the solution of the problem of the dominant set on the visibility graph of the polygon.
Khvatal's art gallery theorem
Khvatal's theorem on an art gallery (Canadian mathematician born in Prague, ) gives the upper bound on the minimum number of guards. The theorem claims that guards are always enough, and sometimes necessary, to guard a simple polygon with tops.
The question of the number of peaks / guards was raised for Khvatal in 1973 by [1] . Enough soon after this proved the theorem [2] . The proof of Khvatal was later simplified by Steve Fisk using 3-color coloring [3] (Fisk was a professor of mathematics at Bowden College [4] ).
Fisk Short Proof
The proof of Steve Fisk [3] is so short and elegant that it is given in the book “ Evidence from the Book ”.
Proof : First, triangulate the polygon (without adding vertices). It can be proved that the vertices of the resulting triangulation graph can be colored in three colors . To show this, we note that a weak dual triangulation graph ( an undirected graph having one vertex for each triangle and one edge for each pair of adjacent triangles) is a tree , since any cycle in the dual graph would form a hole inside the polygon, which contradicts the condition the absence of holes (by hypothesis, the polygon is simple). If there is more than one triangle in a triangulation, the dual graph (like any tree) must have a vertex with only one neighbor, which corresponds to a triangle adjacent to only one other triangle. A polygon with fewer triangles, obtained by removing this extreme triangle, is colored in three colors (we use mathematical induction ), so the coloring can easily be extended to an additional vertex of the deleted triangle.
It is clear that in the resulting 3-color coloring, each triangle must have vertices of all three colors. The vertices of the same color form the correct set of guards, since each triangle is fully visible from the vertex with the selected color. Three colors divide n vertices of the polygon into 3 sets and a color with fewer vertices forms the correct set of guards with a maximum the guards.
Generalizations
The upper border of Khvatal remains true if the guards are not required to be at the vertices of the polygon (but must be inside it).
There are many other generalizations and concretizations of the original gallery theorem [5] . For example, for , in which the edges / walls are at right angles, you only need the guards. There are at least three different proofs of this result, and none of them is simple, this is the proof of Kahn, and [6] , the proof of [7] and the proof of Jörg -Rudiger Sack and Toussin [8] [9] .
A related task asks about the number of guards to block the outer area of an arbitrary polygon (“The Fortress Problem”) - sometimes you need guards and this number is always enough. In other words, an infinite outer region is more difficult to guard than a finite inner region [10] .
Computational complexity
In versions of the gallery protection task, set as the solvability problem , both the polygon and the number k are specified at the input, but the result of solving the problem should be the answer if there are enough k guards to guard the polygon. This task and all its standard options (such as restricting the placement of guards at the vertices or edges of a polygon) are NP-hard [11] [12] [13] . For approximation algorithms of the problem of determining the minimum number of guards, Aidenbenz, Stamm, and Widmeyer [14] proved that the problem is APX-difficult, whence it follows that there is hardly an approximation algorithm of polynomial time with guaranteed efficiency better than some fixed constant. However, the constant of guaranteed efficiency is not known. A logarithmic approximation for the minimum number of guards at the vertex can be obtained by reducing the problem to the problem of the problem of covering a set [15] . As Valtre [16] showed, the set covering problem obtained from the picture gallery problem has a limited Vapnik – Chervonenkis dimension , which allows the use of based set covering algorithms, the guaranteed efficiency of which depends logarithmically on the optimal number guards, and not the number of vertices of the polygon [17] . When the placement of guards is not limited, an infinite number of possible positions of the guards makes the task even more difficult [18] .
However, effective algorithms are known for finding the maximum guards located at the peaks, which corresponds to the upper border of Khvatal. David Avis and Godfried Toussin [19] proved that the placement of security guards can be calculated in the worst case during O (n log n) using the divide and conquer algorithm . Kouches and Moret [20] proposed a linear run time algorithm that uses Fisk's short proof and Bernard Chazell’s planar triangulation algorithm with linear run time.
The exact algorithm for the guards at the tops was proposed by Coute, de Resende, de Souza. The authors conducted intensive computational experiments on some classes of polygons, which showed that optimal solutions can be found in relatively short computational time even for problems with thousands of vertices. Input data and optimal solutions to these problems are available for download [21] .
3D space
If the museum is presented in three-dimensional space as a polyhedron , then the location of the guards at all the peaks does not provide an overview of the entire museum. Although all surfaces of the polyhedron will be observable, for some polyhedra part of the space inside the polyhedron is not observable [22] .
See also
Notes
- ↑ O'Rourke, 1987 , p. one.
- ↑ Chvátal, 1975 .
- ↑ 1 2 Fisk, 1978 .
- ↑ Gemma Leghorn. Mathematics professor dies of leukemia at 63 (Link unavailable) . The Bowdoin Orient (2010). Archived January 16, 2017.
- ↑ Shermer, 1992 .
- ↑ Kahn, Klawe, Kleitman, 1983 .
- ↑ Lubiw, 1985 .
- ↑ O'Rourke, 1987 , p. 31–80.
- ↑ Sack, Toussaint, 1988 .
- ↑ O'Rourke, 1987 , p. 146-154.
- ↑ O'Rourke, 1987 , p. 239-242.
- ↑ Aggarwal, 1984 .
- ↑ Lee, Lin, 1986 .
- ↑ Eidenbenz, Stamm, Widmayer, 2001 .
- ↑ Ghosh, 1987 .
- ↑ Valtr, 1998 .
- ↑ Brönnimann, Goodrich, 1995 .
- ↑ Deshpande, Kim, Demaine, Sarma, 2007 .
- ↑ Avis, Toussaint, 1981 .
- ↑ Kooshesh, Moret, 1992 .
- ↑ Couto, de Rezende, de Souza, 2011 .
- ↑ O'Rourke, 1987 , p. 255.
Literature
- M. Eigler, G. Ziegler. Proof of the Book. The best evidence of the times of Euclid to the present day .. - Moscow: Mir, 2006. - ISBN 5-03-003690-3 UDC 51.1 BBK 22.1.
- A. Aggarwal. The art gallery theorem: Its variations, applications, and algorithmic aspects. - Ph.D. thesis, Johns Hopkins University, 1984.
- D. Avis, GT Toussaint. An efficient algorithm for decomposing a polygon into star-shaped polygons // Pattern Recognition. - 1981. - T. 13 , no. 6 . - S. 395–398 . - DOI : 10.1016 / 0031-3203 (81) 90002-9 .
- H. Brönnimann, MT Goodrich. Almost optimal set covers in finite VC-dimension // Discrete and Computational Geometry. - 1995 .-- T. 14 . - S. 463–479 . - DOI : 10.1007 / BF02570718 .
- V. Chvátal. A combinatorial theorem in plane geometry // Journal of Combinatorial Theory, Series B. - 1975.- T. 18 . - S. 39–41 . - DOI : 10.1016 / 0095-8956 (75) 90061-1 .
- M. Couto, P. de Rezende, C. de Souza. An exact algorithm for minimizing vertex guards on art galleries // International Transactions in Operational Research. - 2011. - DOI : 10.1111 / j.1475-3995.2011.00804.x .
- M. Couto, P. de Rezende, C. de Souza. Benchmark instances for the art gallery problem with vertex guards . - 2011.
- Ajay Deshpande, Taejung Kim, Erik D. Demaine, Sanjay E. Sarma. A Pseudopolynomial Time O (logn) -Approximation Algorithm for Art Gallery Problems // Proc. Worksh. Algorithms and Data Structures . - Springer-Verlag, 2007. - T. 4619. - S. 163–174. - (Lecture Notes in Computer Science). - ISBN 978-3-540-73948-7 . - DOI : 10.1007 / 978-3-540-73951-7_15 .
- S. Eidenbenz, C. Stamm, P. Widmayer. Inapproximability results for guarding polygons and terrains // Algorithmica. - 2001. - T. 31 , no. 1 . - S. 79–113 . - DOI : 10.1007 / s00453-001-0040-8 . Archived June 24, 2003.
- S. Fisk. A short proof of Chvátal's watchman theorem // Journal of Combinatorial Theory, Series B. - 1978.- T. 24 , no. 3 . - S. 374 . - DOI : 10.1016 / 0095-8956 (78) 90059-X .
- SK Ghosh. Proc. Canadian Information Processing Society Congress. - 1987. - S. 429-434 .
- J. Kahn, M. Klawe, D. Kleitman. Traditional galleries require fewer watchmen // SIAM J. Alg. Disc. Meth .. - 1983. - T. 4 , no. 2 . - S. 194–206 . - DOI : 10.1137 / 0604020 .
- AA Kooshesh, BME Moret. Three-coloring the vertices of a triangulated simple polygon // Pattern Recognition. - 1992. - T. 25 , no. 4 . - S. 443 . - DOI : 10.1016 / 0031-3203 (92) 90093-X .
- DT Lee, AK Lin. Computational complexity of art gallery problems // IEEE Transactions on Information Theory. - 1986. - T. 32 , no. 2 . - S. 276–282 . - DOI : 10.1109 / TIT.1986.1057165 .
- A. Lubiw. Decomposing polygonal regions into convex quadrilaterals // Proc. 1st ACM Symposium on Computational Geometry. - 1985. - S. 97-106. - ISBN 0-89791-163-6 . - DOI : 10.1145 / 323233.323247 .
- Joseph O'Rourke. Art Gallery Theorems and Algorithms . - Oxford University Press, 1987. - ISBN 0-19-503965-3 .
- JR Sack, GT Toussaint. Guard placement in rectilinear polygons // Computational Morphology / Toussaint GT. - North-Holland, 1988. - S. 153–176.
- Thomas Shermer. Recent Results in Art Galleries // Proceedings of the IEEE. - 1992. - T. 80 , no. 9 . - S. 1384–1399 . - DOI : 10.1109 / 5.163407 .
- P. Valtr. Guarding galleries where no point sees a small area // Israel J. Math .. - 1998.- T. 104 , no. 1 . - S. 1–16 . - DOI : 10.1007 / BF02897056 .