Проблема с художественной галереей

Проблема с художественной галереей или музейная задача - хорошо изученная проблема видимости в вычислительной геометрии. Это происходит из реальной проблемы охраны художественной галереи с минимальным количеством охранников, которые вместе могут наблюдать за всей галереей. В геометрической версии задачи компоновка художественной галереи представлена ​​простым многоугольником, а каждая защита представлена ​​точкой точкой в многоугольнике. Считается, что набор $S\; \{\backslash \; displaystyle\; S\}$точек охраняет многоугольник, если для каждой точки $p\; \{\backslash \; displaystyle\; p\}$в многоугольнике существует является некоторым $q\; \in \; S\; \{\backslash \; displaystyle\; q\; \backslash \; in\; S\}$таким, что отрезок между $p\; \{\backslash \; displaystyle\; p\}$и $q\; \{\backslash \; displaystyle\; q\}$не покидает многоугольник.

• 1 Два измерения
  • 1.1 Теорема Хватала о художественной галерее
  • 1.2 Краткое доказательство Фиска
  • 1.3 Обобщения
  • 1.4 Вычислительная сложность
• 2 Три измерения
• 3 См. Также
• 4 Примечания
• 5 Источники

Эту галерею покрывают четыре камеры.

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

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

Теорема Хватала о художественной галерее

Теорема Хватала о художественной галерее, названная в честь Вацлава Хватала, дает верхнюю границу минимального количества охранников. В нем говорится, что $\lfloor \; n\; /\; 3\; \rfloor \; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; lfloor\; n\; /\; 3\; \backslash \; right\; \backslash \; rfloor\}$охранников всегда достаточно, а иногда необходимо, чтобы охранять простой многоугольник с помощью $n\; \{\; \backslash \; displaystyle\; n\}$вершин.

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

Краткое доказательство Фиска

3-раскраска вершин треугольного многоугольника. Синие вершины образуют набор из трех стражей, минимальное количество которых гарантируется теоремой о художественной галерее. Однако этот набор не является оптимальным: один и тот же многоугольник может охраняться только двумя охранниками.

Доказательство Стива Фиска настолько короткое и элегантное, что его выбрали для включения в Доказательства из КНИГИ. Доказательство выглядит следующим образом:

Во-первых, многоугольник триангулирован (без добавления дополнительных вершин). Вершины получившегося триангуляционного графа могут быть трехцветными. Ясно, что при трехцветной раскраске каждый треугольник должен иметь все три цвета. Вершины любого одного цвета образуют допустимый защитный набор, потому что каждый треугольник многоугольника охраняется его вершиной этого цвета. Поскольку три цвета разделяют n вершин многоугольника, цвет с наименьшим количеством вершин определяет допустимый защитный набор с не более чем $\lfloor \; n\; /\; 3\; \rfloor \; \{\backslash \; displaystyle\; \backslash \; lfloor\; n\; /\; 3\; \backslash \; rfloor\}$охранники.

Обобщения

Верхняя граница Хватала остается в силе, если ограничение на охранников в углах ослаблено на охранников в любой точке, не внешней по отношению к многоугольнику.

Есть ряд других обобщений и специализаций исходной теоремы о художественной галерее. Например, для ортогональных многоугольников, чьи края / стены пересекаются под прямым углом, только $\lfloor \; n\; /\; 4\; \rfloor \; \{\backslash \; displaystyle\; \backslash \; lfloor\; n\; /\; 4\; \backslash \; rfloor\}$охраняет нужны. Есть по крайней мере три различных доказательства этого результата, ни одно из них не простое: Кан, Клаве и Клейтман ; автор Любив ; и Мешком и Туссеном.

. Связанная задача спрашивает количество охранников, которые должны покрыть внешнюю часть произвольного многоугольника («Проблема Крепости»): $\lceil \; n\; /\; 2\; \rceil \; \{\backslash \; displaystyle\; \backslash \; lceil\; n\; /\; 2\; \backslash \; rceil\}$иногда необходимы и всегда достаточно. Другими словами, бесконечное внешнее пространство сложнее охватить, чем конечное внутреннее.

Вычислительная сложность

В проблеме решения версии задачи художественной галереи дается одна в качестве входных данных и многоугольник, и число k, и необходимо определить, можно ли защитить многоугольник с помощью k или меньшего числа охранников. Эта проблема имеет вид $\exists \; R\; \{\backslash \; displaystyle\; \backslash \; exists\; \backslash \; mathbb\; \{R\}\}$-complete, как и версия, в которой ограждения ограничены краями многоугольника. Более того, большинство других стандартных вариантов (таких как ограничение расположения защитных элементов вершинами) являются NP-трудными.

Что касается алгоритмов аппроксимации для минимального количества охранников, Eidenbenz, Stamm Widmayer (2001) доказал, что проблема сложна для APX, подразумевая, что маловероятно, что любое отношение приближения, лучше, чем некоторая фиксированная константа, может быть достигнуто с помощью полиномиального времени алгоритм аппроксимации. Однако до недавнего времени не был известен алгоритм достижения постоянного отношения приближения. Гош (1987) показал, что логарифмическое приближение может быть достигнуто для минимального количества защитных элементов вершин путем дискретизации входного многоугольника на выпуклые подобласти и последующего сведения проблемы к множеству . крышка проблема. Как показал Валтр (1998), система множеств, полученная из задачи художественной галереи, имеет ограниченное измерение VC, что позволяет применять алгоритмы множественного покрытия на основе ε-сетей, коэффициент аппроксимации которого является логарифмом оптимального числа охранников, а не числа вершин многоугольника. Для неограниченных охранников бесконечное количество потенциальных позиций охранников еще больше усложняет задачу. Однако, ограничивая ограждения на мелкой сетке, можно получить более сложный алгоритм логарифмической аппроксимации при некоторых мягких дополнительных предположениях, как показано Bonnet Miltzow (2017). Однако известны эффективные алгоритмы для поиска набора не более $\lfloor \; n\; /\; 3\; \rfloor \; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; lfloor\; n\; /\; 3\; \backslash \; right\; \backslash \; rfloor\}$защитных ограждений вершин, соответствующих верхней границе Хватала. Дэвид Эвис и Годфрид Туссен (1981) доказали, что размещение этих охранников может быть вычислено за O (n log n) в худшем случае с помощью алгоритм «разделяй и властвуй». Kooshesh Moret (1992) представили алгоритм линейного времени, используя краткое доказательство Фиска и алгоритм линейной триангуляции на плоскости во времени Бернарда Шазелла.

Для простых многоугольников, не содержащих дыр, существование алгоритма аппроксимации постоянного множителя для защиты вершин и краев было предположено Гошем. Первоначально было показано, что гипотеза Гоша верна для защиты вершин в двух специальных подклассах простых многоугольников, а именно. монотонные многоугольники и многоугольники, слабо заметные с ребра. Krohn Nilsson (2013) представили алгоритм аппроксимации, который вычисляет за полиномиальное время набор защиты вершин для монотонного многоугольника, так что размер набора защиты не более чем в 30 раз превышает оптимальное количество защитных элементов вершин. Bhattacharya, Ghosh Roy (2017) представили алгоритм аппроксимации, который вычисляет за O (n) раз набор защиты вершин для простого многоугольника, который слабо виден с края, так что размер набора защиты равен не более чем в 6 раз больше оптимального числа защитников вершин. Впоследствии Бхаттачарья, Гош и Пал (2017) заявили, что полностью разрешили эту гипотезу, представив алгоритмы аппроксимации постоянного множителя для защиты общих простых многоугольников с использованием защиты вершин и защиты краев. Для вершин, охраняющих подкласс простых многоугольников, которые слабо видны с ребра, схема аппроксимации за полиномиальное время была предложена Ашуром и др. (2019).

Точный алгоритм был предложен Couto, de Rezende de Souza (2011) ошибка harvtxt: несколько целей (2 ×): CITEREFCoutode_Rezendede_Souza2011 (help ) для вершины охранники. Авторы провели обширные вычислительные эксперименты с несколькими классами многоугольников, показав, что оптимальные решения могут быть найдены за относительно небольшое время вычислений даже для экземпляров, связанных с тысячами вершин. Исходные данные и оптимальные решения для этих случаев доступны для загрузки.

Пример многогранника с внутренними точками, не видимыми ни из одной вершины.

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

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