On Some Variations of the Problem of Protecting the Art Gallery
УДК 519.67
Abstract
Video cameras are the most common and affordable means of security. What is captured by the camera lens is transmitted to the video surveillance monitor screens in the security room. It is important to reduce the number of the monitor screens to a minimum and place the surveillance cameras to cover the entire protected areas. Reducing the number of video cameras helps significantly reduce the price of the entire surveillance system. A series of problems on the protection of an art gallery are devoted to the optimization of security systems. Currently, art gallery security problems are fairly well-studied visibility problems in computational geometry. It can be seen as the problem of using the least number of surveillance cameras to provide video coverage of all the rooms and halls of an art gallery. In the twodimensional case, the gallery layout is represented as a simple polygon, with the guard as a point inside it.
This paper considers two variations of the problem: the guard route problem and the problem of guarding an art gallery on the surface of a convex polyhedron. These problems were considered in the works of many mathematicians. The paper provides a description of algorithms for solving these problems and pseudocodes of the main procedures necessary to implement these algorithms in the Python programming language.
Downloads
Metrics
References
Берг М.,Чеонг О., Кревельд М., Овермарс М. Вычислительная геометрия. Алгоритмы и приложения / пер. с англ. А.А. Слинкин. М., 2017. 438 с. DOI: 10.1007/978-3540-77974-2
Chvatal V. A Combinatorial Theorem in Plane Geometry // Journal of Combinatorial Theory, Series B. 1975. Vol. 18. P. 39-41. DOI: 10.1016/0095-8956(75)90061-1
Fisk S. A Short Proof of Chvatal’s Watchman Theorem // Journal of Combinatorial Theory, Series B. 1978. Vol. 24. No 3. P. 374. DOI: 10.1016/0095-8956(78)90059-X
Kahn J., Klawe M., Kleitman D. Traditional Galleries Require Fewer Watchmen // SIAM Journal on Algebraic and Discrete Methods. 1983. Vol. 4. No 2. P. 194-206. DOI: 10.1137/0604020
Lubiw A. Decomposing Polygonal Regions into Convex Quadrilaterals // Proc. 1st ACM Symposium on Computational Geometry. Department of Computer Science University of Toronto. Toronto, Canada. ACM Digital Library. 1985. P. 97-106. DOI: 10.1145/323233.323247
Sack J.R., Toussaint G.T. Guard Placement in Rectilinear Polygons // Computational Morphology. 1988. Vol. 6. No C. P. 153-176. DOI: 10.1016/B978-0-444-70467-2.50016-3
Carlsson S., Jonsson H., Nilsson B. Finding the Shortest Watchman Route in a Simple Polygon // Discrete and Computational Geometry. 1999. Vol. 22. No 3. P. 77-402. DOI: 10.1007/PL00009467
Chin W, Ntafos S. Shortest Watchman Routes in Simple Polygons // Discrete and Computational Geometry. 1991. Vol. 6. No 1. P. 9-31. DOI: 10.1007/BF02574671
Chazelle B., Edelsbrunner H. An Optimal Algorithm for Intersecting Line Segments in the Plane // Journal of the ACM. 1992. Vol. 39. No 1. P. 1-54. DOI: 10.1145/147508.147511
O’Rourke Joseph. An Alternate Proof of the Rectilinear Art Gallery Theorem // Journal of Geometry. 1983. Vol. 21. P. 119-130. DOI: 10.1007/BF01918136
Nishizeki T. Lower Bounds on the Cardinality of the Maximum Matchings of Planar Graphs // Discrete Mathematics. 1979. Vol. 28. No 3. P. 255-267. DOI: 10.1016/0012-365X(79)90133-X
Balinski M.L. On the Graph Structure of Convex Polyhedral in n-space // Pacific Journal of Mathematics. 1961. Vol. 11. No 2. P. 224-227. DOI: 10.2140/pjm.1961.11.431
Ivanov M. Edmonds Algorithm for Finding the Greater Matching in Arbitrary Graphs. E-maxx.ru: Information and Reference Portal. URL: https://emaxx.ru/algo/matchinged-monds (accessed: 06.12.2012).
Copyright (c) 2024 Александр Владимирович Гринкевич, Дмитрий Николаевич Оскорбин, Егор Дмитриевич Титов
This work is licensed under a Creative Commons Attribution 4.0 International License.
Izvestiya of Altai State University is a golden publisher, as we allow self-archiving, but most importantly we are fully transparent about your rights.
Authors may present and discuss their findings ahead of publication: at biological or scientific conferences, on preprint servers, in public databases, and in blogs, wikis, tweets, and other informal communication channels.
Izvestiya of Altai State University allows authors to deposit manuscripts (currently under review or those for intended submission to Izvestiya of Altai State University) in non-commercial, pre-print servers such as ArXiv.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY 4.0) that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
