О некоторых вариациях задач об охране картинной галереи

Abstract

Видеокамеры являются наиболее распространенным и доступным средством охраны. То, что попадает в объектив камеры, передается на экраны мониторов в помещении охраны. Важно, чтобы количество мониторов было сведено к минимуму, при этом камеры должны размещаться таким образом, чтобы все помещение находилось под охраной. Уменьшение числа видеокамер позволяет уменьшить цену всей системы наблюдения. Оптимизации систем защиты посвящена серия задач об охране картинной галереи. В настоящее время задачи об охране картинной галереи являются достаточно хорошо изученными задачами видимости в вычислительной геометрии. Они возникли как задачи охраны некоторой художественной галереи наименьшим числом средств наблюдения, которые обозревают все ее залы. В двумерном случае план галереи представлен в виде простого многоугольника, охранник — точкой внутри него. В данной работе рассматриваются две вариации задачи: проблема сторожевого маршрута и задача об охране картинной галереи на поверхности выпуклого многогранника. Эти задачи рассматривались в работах многих математиков. Нами приводятся описание алгоритмов решения этих задач и псевдокоды основных процедур, необходимых для реализации этих алгоритмов на языке программирования Python.

Keywords

• максимальное паросочетание
• сторожевой маршрут
• простой многоугольник
• алгоритм расстановки охранников
• разрез
• рефлективная вершина
• триангуляция
• двойственный граф многогранника