Введение

Математическая задача
Задача об охранниках в художественной галерее или музее — хорошо изученная задача о видимости в вычислительной геометрии. Она возникла из следующей практической проблемы:

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

Двумерность

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

Теорема о галерее искусств Шваталя

Теорема о художественной галерее Чваталя, названная в честь Вацлава Чваталя, устанавливает верхнюю границу минимального количества охранников. Она утверждает:

"Для наблюдения за простым многоугольником с *n* вершинами всегда достаточно ⌊*n*/3⌋ охранников, и в некоторых случаях это количество необходимо."

История

Вопрос о том, сколько вершин/наблюдателей/охранников необходимо, был задан Хва́талу Виктором Кли в 1973 году. Хва́тал доказал это вскоре после этого. Доказательство Хва́тала позднее было упрощено Сти́веном Фиском с помощью аргумента о 3-раскраске. Хва́тал использует более геометрический подход, в то время как Фиск опирается на известные результаты из теории графов.

Иллюстрация доказательства

Чтобы проиллюстрировать доказательство, рассмотрим многоугольник, изображенный ниже. Первый шаг — триангулировать многоугольник (см. рисунок 1). Затем применяется правильная раскраска (рисунок 2), и мы видим, что есть красные, синие и зеленые вершины. Цвет, представленный наименьшим количеством вершин, — синий или красный, следовательно, многоугольник можно охранять с помощью охранников (рисунок 3). Это согласуется с теоремой о художественной галерее, поскольку у многоугольника вершин, и .

Обобщения

Верхняя граница Хватала остаётся справедливой, если ограничение на размещение охраны в углах ослаблено до размещения охраны в любой точке, не лежащей вне полигона. Существует ряд других обобщений и специализаций исходной теоремы о художественной галерее. Например, для ортогональных многоугольников, у которых рёбра/стены пересекаются под прямым углом, требуется только ⌈n/3⌉ охранников. Существует по крайней мере три различных доказательства этого результата, ни одно из которых не является простым: доказательства, предложенные Каном, Клау и Клейтманом; Любивом; и Саком и Туссентом. Связанная задача заключается в определении минимального числа охранников, необходимых для покрытия внешней области произвольного многоугольника ("Задача о крепости"): ⌈n⌉ охранников иногда необходимы и всегда достаточны, если охранники размещены на границе многоугольника, в то время как ⌈n/2⌉ охранников иногда необходимы и всегда достаточны, если охранники размещены в любой точке внешней области многоугольника. Иными словами, бесконечная внешняя область сложнее для покрытия, чем конечная внутренняя область.

Комплексность вычислений

В вариантах задачи о галерее, рассматриваемых как задача принятия решений, на вход подается многоугольник и число k, и требуется определить, можно ли охранять многоугольник с помощью k или меньшего числа охранников. Эта задача является NP-полной, как и ее вариант, где охранники ограничены сторонами многоугольника. Более того, большинство других стандартных вариаций (например, ограничение расположения охранников вершинами) являются NP-трудными. Что касается алгоритмов аппроксимации для минимального числа охранников, то было доказано, что задача является APX-трудной, что подразумевает маловероятность существования алгоритма аппроксимации в полиномиальное время с коэффициентом аппроксимации лучше некоторой фиксированной константы. Показано, что логарифмическая аппроксимация может быть достигнута для минимального числа охранников вершин путем дискретизации входного многоугольника на выпуклые подрегионы и последующего сведения задачи к задаче о покрытии множеством. Как показано, система множеств, полученная из задачи о галерее, имеет ограниченную размерность VC, что позволяет применять алгоритмы покрытия множеством, основанные на ε-сетях, коэффициент аппроксимации которых является логарифмом оптимального числа охранников, а не числа вершин многоугольника. Для неограниченных охранников бесконечное число потенциальных позиций охранников делает задачу еще более сложной. Однако, ограничивая охранников размещением на мелкой сетке, можно получить более сложный алгоритм логарифмической аппроксимации при некоторых дополнительных предположениях, как показано. Эффективные алгоритмы известны для нахождения множества не более чем из охранников вершин, соответствующих верхней границе, установленной Chvátal. Доказано, что размещение этих охранников может быть вычислено за время O(n log n) в худшем случае с помощью алгоритма "разделяй и властвуй". Предложен алгоритм с линейным временем, использующий короткое доказательство Фиска и алгоритм линейной триангуляции плоскости Бернарда Шазеля. Для простых многоугольников без отверстий, Гош предположил существование алгоритма аппроксимации с постоянным коэффициентом для охранников вершин и сторон. Предположение Гоша было первоначально подтверждено для охранников вершин в двух специальных подклассах простых многоугольников, а именно монотонных многоугольников и многоугольников, слабо видимых с ребра. Представлен алгоритм аппроксимации, который за полиномиальное время вычисляет множество охранников вершин для монотонного многоугольника, размер которого не превышает 30 оптимального числа охранников вершин. Представлен алгоритм аппроксимации, который за время O(n²) вычисляет множество охранников вершин для простого многоугольника, слабо видимого с ребра, размер которого не превышает 6 оптимального числа охранников вершин. Впоследствии, заявил, что полностью решил проблему, представив алгоритмы аппроксимации с постоянным коэффициентом для охраны общих простых многоугольников с использованием охранников вершин и сторон. Для охраны подкласса простых многоугольников, слабо видимых с ребра, была предложена схема аппроксимации полиномиального времени. Авторы провели обширные вычислительные эксперименты с несколькими классами многоугольников, показав, что оптимальные решения могут быть найдены за относительно небольшое время вычислений даже для экземпляров, связанных с тысячами вершин. Входные данные и оптимальные решения для этих экземпляров доступны для скачивания.

Три измерения

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