Задача об охране картинной галереи в случае ортогонального многоугольника

УДК 519.67 ББК 22.1я431

  • Александр Владимирович Гринкевич Алтайский государственный университет Email: alexander.grin97@gmail.com
  • Дмитрий Николаевич Оскорбин Алтайский государственный университет Email: oskorbin@yandex.ru

Abstract

Статья посвящена исследованию задачи об охране картинной галереи, когда план ее интерьера представлен в виде ортогонального многоугольника. Проводится обзор известных результатов, и получен псевдокод алгоритма расстановки охранников

Author Biographies

Александр Владимирович Гринкевич, Алтайский государственный университет

Алтайский государственный университет, институт математики и информационных технологий, студент

Дмитрий Николаевич Оскорбин, Алтайский государственный университет

кандидат физико-математическихнаук, Алтайский государственный университет, Институт математики и информационных технологий, доцент кафедры мат. ан-за

References

1. O'Rourke, Joseph. Art Gallery Theorems and Algorithms // Oxford University Press. – 1987.
2. A. Lubiw. Decomposing polygonal regions into convex quadrilaterals // Proc. 1st ACM Symposium on Computational Geometry. – 1985. – С. 97–106.
3. J. Kahn, M. Klawe, D. Kleitman. Traditional galleries require fewer watchmen // SIAM J. Alg. Disc. Meth. – 1983. – Т. 4, вып. 2. – С. 194–206.
4. J. R. Sack, G. T. Toussaint. Guard placement in rectilinear polygons // Computational Morphology / Toussaint G. T. – North-Holland, 1988. –С. 153–176.
5. O'Rourke, Joseph. An alternate proof of the rectilinear art gallery theorem // Journal of Geometry, vol. 21. – 1983. – C. 119–130.
Published
2021-07-22