Задача об охране картинной галереи на клетчатой плоскости

  • А.В. Гринкевич Алтайский государственный университет
  • Д.Н. Оскорбин Алтайский государственный университет
  • Д.В. Вылегжанин Белорусский государственный университет
Ключевые слова: вычислительная геометрия, ортогональный многоугольник, задача об охране картинной галереи

Аннотация

В данной работе рассматривается задача об охране картинной галереи в случае, когда план галереи представляет собой ортогональный многоугольник с вершинами в узлах целочисленной решетки. Проводится точная оценка на число охранников, а также разрабатывается жадный алгоритм расстановки охранников. Для реализации алгоритма выбран язык программирования Python.

Литература

1. O'Rourke J. Art Gallery Theorems and Algorithms. – New York : Oxford University Press, 1987. – 282 p.
2. Chvatal V. A combinatorial theorem in plane geometry // Journal of Combinatorial Theory, Series B. – 1975. – Vol. 18. – P. 39-41.
3. Fisk S. A short proof of Chvatal's watchman theorem // Journal of Combinatorial Theory, Series B. – 1978. – Vol. 24, no. 3. – P. 374.
4. Берг М., Чеонг О., Кревельд М., Овермарс М. Вычислительная геометрия. Алгоритмы и приложения. - М. : ДМК Пресс, 2017. - 438 с.
Опубликован
2020-12-01
Как цитировать
1. Гринкевич А., Оскорбин Д., Вылегжанин Д. Задача об охране картинной галереи на клетчатой плоскости // Труды семинара по геометрии и математическому моделированию, 2020. № 6. С. 9-13. URL: http://journal.asu.ru/psgmm/article/view/8840.

Наиболее читаемые статьи этого автора (авторов)