О некоторых вариациях задач об охране картинной галереи
УДК 519.67
Аннотация
Видеокамеры являются наиболее распространенным и доступным средством охраны. То, что попадает в объектив камеры, передается на экраны мониторов в помещении охраны. Важно, чтобы количество мониторов было сведено к минимуму, при этом камеры должны размещаться таким образом, чтобы все помещение находилось под охраной. Уменьшение числа видеокамер позволяет уменьшить цену всей системы наблюдения. Оптимизации систем защиты посвящена серия задач об охране картинной галереи. В настоящее время задачи об охране картинной галереи являются достаточно хорошо изученными задачами видимости в вычислительной геометрии. Они возникли как задачи охраны некоторой художественной галереи наименьшим числом средств наблюдения, которые обозревают все ее залы. В двумерном случае план галереи представлен в виде простого многоугольника, охранник — точкой внутри него.
В данной работе рассматриваются две вариации задачи: проблема сторожевого маршрута и задача об охране картинной галереи на поверхности выпуклого многогранника. Эти задачи рассматривались в работах многих математиков. Нами приводятся описание алгоритмов решения этих задач и псевдокоды основных процедур, необходимых для реализации этих алгоритмов на языке программирования Python.
Скачивания
Metrics
Литература
Берг М.,Чеонг О., Кревельд М., Овермарс М. Вычислительная геометрия. Алгоритмы и приложения / пер. с англ. А.А. Слинкин. М., 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 Александр Владимирович Гринкевич, Дмитрий Николаевич Оскорбин, Егор Дмитриевич Титов
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
