Введем понятие художественной галереи. Это здание, в котором любая конфигурация, которая визуально покрывает стены, обязательно покрывает всю галерею. Любая галерея с не более чем двумя рефлекторными углами является классической. Алгоритм полиномиального времени предоставляется для определения того, существует ли для данной галереи конечный набор позиций.

Введение и основные результаты

Понятие классической художественной галереи представляет собой простой многоугольник (граница представляет собой простую замкнутую кривую, состоящую из конечного числа отрезков), а охрана — обозначенная точка в галерее. Охранник в художественной галерее визуально покрывает каждую точку, для которой сегмент целиком находится внутри. Конфигурация охранников, которая визуально покрывает галерею, представляет собой набор точек в галерее, так что каждая точка визуально покрывается, по меньшей мере, одним из охранников. Известно, что галерея с углами всегда может быть визуально покрыта конфигурацией охранников. Предмет визуального покрытия художественных галерей развился довольно существенно с этой работы, например, путем ограничения или расширения рассматриваемых типов полигонов (ортогональных многоугольников или многоугольников с отверстиями). Мы рассматриваем связь между визуальным освещением стен и остальной галереей.

Конфигурация художественной галереи

Художественная галерея называется классической, если любая конфигурация ограждений, которая визуально покрывает стенки галереи, обязательно покрывает всю галерею. Обратите внимание, что с практической точки зрения проверка того, что конфигурация ограждений покрывает стенки галереи, может быть более простой задачей, чем проверка того, охватывает ли она всю галерею. Например, могут возникнуть ситуации, при которых легко управлять датчиком (или каким-либо другим типом управления) вдоль стен, в то время как доступ к внутренней части каким-то образом ограничен. Если мы знаем, что галерея нормальная, и у нас есть способ контролировать, что стены визуально покрыты во все времена, тогда, пока стены покрыты, мы уверены, что охранники покрывают всю галерею. В такой ситуации, пока стены покрыты, мы можем даже допускать относительно свободное перемещение охранников в галерее без необходимости постоянно направлять их, общаться с ними или даже иметь информацию об их местоположении. Терминология для обычных галерей моделируется, хотя и поверхностно, по терминологии, используемой для нормальных расширений поля. Мы предоставляем два независимых и достаточных условия для нормальной работы галереи. Напомним, что угол рефлекса в галерее — это угол, в котором внутренний угол больше 180 градусов. В каждой галерее не более двух рефлекторных углов.