Задача об охране картинной галереи в случае ортогонального многоугольника
УДК 519.67 ББК 22.1я431
Ключевые слова:
вычислительная геометрия, ортогональный многоугольник, алгоритм расстановки охранников, задача об охране картинной галереи
Аннотация
Статья посвящена исследованию задачи об охране картинной галереи, когда план ее интерьера представлен в виде ортогонального многоугольника. Проводится обзор известных результатов, и получен псевдокод алгоритма расстановки охранников
Литература
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.
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.
Опубликован
2021-07-22
Раздел
Секция ГЕОМЕТРИЯ И ПРИКЛАДНОЙ МАТЕМАТИЧЕСКИЙ АНАЛИЗ
