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

Математическая задача

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

« Каково минимальное количество охранников в художественной галерее , которые вместе могут наблюдать за всей галереей?»

В геометрической версии задачи макет художественной галереи представлен простым многоугольником , а каждый охранник представлен точкой в ​​многоугольнике. Говорят, что набор точек охраняет многоугольник, если для каждой точки в многоугольнике есть некоторые такие, что отрезок прямой между и не покидает многоугольник. ${\displaystyle S}$ ${\displaystyle p}$ ${\displaystyle q\in S}$ ${\displaystyle p}$ ${\displaystyle q}$

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

Два измерения

Эту галерею могут охранять четыре охранника.

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

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

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

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

«Чтобы защитить простой многоугольник с вершинами, всегда достаточно иметь охрану, а иногда она просто необходима». ${\displaystyle n}$ ${\displaystyle \left\lfloor n/3\right\rfloor }$

История

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

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

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

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

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

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

Для иллюстрации доказательства рассмотрим многоугольник ниже. Первым шагом является триангуляция многоугольника (см. Рисунок 1 ). Затем применяется правильная -раскраска ( Рисунок 2 ) и наблюдается наличие  красных,  синих и  зеленых вершин. Цвет с наименьшим количеством вершин - синий или красный, поэтому многоугольник может быть покрыт  охранниками ( Рисунок 3 ). Это согласуется с теоремой о художественной галерее, поскольку многоугольник имеет  вершины, и . ${\displaystyle 3}$ ${\displaystyle 4}$ ${\displaystyle 4}$ ${\displaystyle 6}$ ${\displaystyle 4}$ ${\displaystyle 14}$ ${\displaystyle \left\lfloor {\frac {14}{3}}\right\rfloor =4}$

• 
  Рисунок 1
• 
  Рисунок 2
• 
  Рисунок 3

Обобщения

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

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

В смежной задаче требуется определить количество охранников для покрытия внешней части произвольного многоугольника («задача крепости»): иногда необходимо и всегда достаточно, если охранники размещены на границе многоугольника, в то время как иногда необходимо и всегда достаточно, если охранники размещены в любом месте внешней части многоугольника. ^[9] Другими словами, бесконечную внешнюю часть сложнее покрыть, чем конечную внутреннюю часть. ${\displaystyle \lceil n/2\rceil }$ ${\displaystyle \lceil n/3\rceil }$

Сложность вычислений

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

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

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

Точный алгоритм был предложен Couto, de Rezende & de Souza (2011) для vertex guards. Авторы провели обширные вычислительные эксперименты с несколькими классами полигонов, показывающие, что оптимальные решения могут быть найдены за относительно небольшое время вычислений даже для экземпляров, связанных с тысячами вершин. Входные данные и оптимальные решения для этих экземпляров доступны для загрузки. ^[13]

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

Ортогональный многогранник , каждая вершина которого невидима из его середины ^[14]

Пример многогранника с внутренними точками, не видимыми ни из одной вершины; на рисунке справа показано поперечное сечение, проходящее через его середину, O, параллельно ABCD.

360° сферическая панорама изнутри многогранника выше, показывающая, что все вершины скрыты желтыми гранями
( просмотр как 360° интерактивной панорамы )

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

Смотрите также

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

Примечания

1. Чтобы доказать 3-раскрашиваемость триангуляций многоугольников, мы замечаем, что слабый двойственный граф к триангуляции ( неориентированный граф, имеющий одну вершину на треугольник и одно ребро на пару смежных треугольников) является деревом , поскольку любой цикл в двойственном графе будет образовывать границу дыры в многоугольнике, вопреки предположению, что в нем нет дыр. Всякий раз, когда есть более одного треугольника, двойственный граф (как и любое дерево) должен иметь вершину только с одним соседом, что соответствует треугольнику, который смежн с другими треугольниками только по одной из своих сторон. Меньший многоугольник, образованный удалением этого треугольника, имеет 3-раскраску по математической индукции , и эта раскраска легко распространяется на одну дополнительную вершину удаленного треугольника. ^[5]

Ссылки

1. О'Рурк (1987), стр. 1.
2. Хватал (1975).
3. Фиск (1978).
4. Айгнер и Циглер (2018).
5. О'Рурк (1987), стр. 13.
6. Шермер (1992); Уррутия (2000)
7. Кан, Клэве и Клейтман (1983); Любив (1985); Сак и Туссен (1988).
8. О'Рурк (1987), стр. 31–80.
9. О'Рурк (1987), стр. 146–154.
10. Абрахамсен, Адамашек и Мильцов (2022).
11. О'Рурк и Суповит (1983); Ли и Лин (1986).
12. Бренниманн и Гудрич (1995).
13. Коуто, де Резенде и де Соуза (2011).
14. Эрик Липка, Заметка о галереях минимализма , 2019.
15. О'Рурк (1987), стр. 255.

Источники

• Абрахамсен, Миккель; Адамашек, Анна; Мильцов, Тиллманн (2022), «Проблема художественной галереи является полной», Журнал ACM , 69 (1): A4:1–A4:70, arXiv : 1704.06969 , doi : 10.1145/3486220, MR  4402363, S2CID  245059672 ${\displaystyle \exists {\mathbb {R}}}$
• Аггарвал, А. (1984), Теорема о художественной галерее: ее вариации, приложения и алгоритмические аспекты , докторская диссертация, Университет Джонса Хопкинса.
• Айгнер, Мартин ; Циглер, Гюнтер М. (2018), «Глава 40: Как охранять музей», Корректуры из THE BOOK (6-е изд.), Берлин: Springer, стр. 281–283, doi :10.1007/978-3-662-57265-8, ISBN 978-3-662-57264-1, г-н  3823190.
• Ashur, Stav; Filtser, Omrit; Katz, Matthew J.; Saban, Rachel (2019), «Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains», в Bampis, Evripidis; Megow, Nicole (ред.), Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Мюнхен, Германия, 12–13 сентября 2019 г., Revised Selected Papers , Lecture Notes in Computer Science, т. 11926, Берлин: Springer, стр. 1–17, doi : 10.1007/978-3-030-39479-0_1, ISBN 978-3-030-39478-3, S2CID  210936577.
• Avis, D. ; Toussaint, GT (1981), "Эффективный алгоритм разложения многоугольника на звездообразные многоугольники" (PDF) , Pattern Recognition , 13 (6): 395–398, Bibcode :1981PatRe..13..395A, doi :10.1016/0031-3203(81)90002-9.
• Бхаттачарья, Притам; Гхош, Субир Кумар; Пал, Судебкумар (2017), Алгоритмы постоянной аппроксимации для защиты простых многоугольников с использованием вершинных защит , arXiv : 1712.05492
• Бхаттачарья, Притам; Гхош, Субир Кумар; Рой, Бодхаян (2017), «Аппроксимируемость защиты полигонов со слабой видимостью», Discrete Applied Mathematics , 228 : 109–129, arXiv : 1409.4621 , doi : 10.1016/j.dam.2016.12.015, MR  3662965, S2CID  9916523
• Бонне, Эдуард; Мильцов, Тильманн (2017), «Алгоритм аппроксимации проблемы художественной галереи», Аронов, Борис; Кац, Мэтью Дж. (ред.), 33-й Международный симпозиум по вычислительной геометрии, SoCG 2017, 4–7 июля 2017 г., Брисбен, Австралия , LIPics, vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 20:1–20:15, arXiv : 1607.05527 , doi : 10.4230/LIPIcs.SoCG.2017.20 , MR  3685692, S2CID  1293138.
• Brönnimann, H.; Goodrich, MT (1995), «Почти оптимальные покрытия множеств в конечной размерности VC», Discrete and Computational Geometry , 14 (1): 463–479, doi : 10.1007/BF02570718.
• Chvátal, V. (1975), «Комбинаторная теорема в плоской геометрии», Журнал комбинаторной теории, Серия B , 18 : 39–41, doi : 10.1016/0095-8956(75)90061-1.
• Couto, M.; de Rezende, P.; de Souza, C. (2011), «Точный алгоритм минимизации вершинных защит в художественных галереях», International Transactions in Operational Research , 18 (4): 425–448, doi :10.1111/j.1475-3995.2011.00804.x.
• де Резенде, П.; де Соуза, К.; Коуто, М.; Тозони, Д. (2011), «Проблема художественной галереи с защитой вершин», Проект художественной галереи , Instituto de Computação.
• Дешпанде, Аджай; Ким, Тэджунг; Демейн, Эрик Д.; Сарма, Санджай Э. (2007), "Алгоритм псевдополиномиального времени O(logn)-аппроксимации для задач художественной галереи", Proc. Worksh. Алгоритмы и структуры данных , Lecture Notes in Computer Science, т. 4619, Springer-Verlag, стр. 163–174, doi : 10.1007/978-3-540-73951-7_15, hdl : 1721.1/36243 , ISBN 978-3-540-73948-7, S2CID  9148459.
• Eidenbenz, S.; Stamm, C.; Widmayer, P. (2001), "Результаты неаппроксимируемости для защиты полигонов и ландшафтов" (PDF) , Algorithmica , 31 (1): 79–113, doi :10.1007/s00453-001-0040-8, S2CID  14532511, архивировано из оригинала (PDF) 24.06.2003.
• Фиск, С. (1978), «Краткое доказательство теоремы Хватала о стороже», Журнал комбинаторной теории, Серия B , 24 (3): 374, doi : 10.1016/0095-8956(78)90059-X.
• Гош, СК (1987), «Алгоритмы аппроксимации для задач художественной галереи», Труды Конгресса Канадского общества обработки информации , стр. 429–434.
• Кан, Дж.; Клаве, М .; Клейтман, Д. (1983), «Традиционные галереи требуют меньше смотрителей», SIAM J. Algebr. Discrete Methods , 4 (2): 194–206, doi :10.1137/0604020.
• Кушеш, А.А.; Морет, Б.М.Е. (1992), «Трехцветная раскраска вершин триангулированного простого многоугольника», Pattern Recognition , 25 (4): 443, Bibcode : 1992PatRe..25..443K, doi : 10.1016/0031-3203(92)90093-X.
• Krohn, Erik A.; Nilsson, Bengt J. (2013), «Приближенная охрана монотонных и прямолинейных многоугольников», Algorithmica , 66 (3): 564–594, doi :10.1007/s00453-012-9653-3, hdl : 2043/11487 , MR  3044626, S2CID  1458082.
• Ли, Д.Т .; Лин, А.К. (1986), «Вычислительная сложность задач художественной галереи», Труды IEEE по теории информации , 32 (2): 276–282, doi :10.1109/TIT.1986.1057165.
• Любив, А. (1985), «Разложение многоугольных областей на выпуклые четырехугольники», Труды 1-го симпозиума ACM по вычислительной геометрии , стр. 97–106, doi :10.1145/323233.323247, ISBN 0-89791-163-6, S2CID  15752916.
• О'Рурк, Джозеф (1987), Теоремы и алгоритмы художественной галереи , Oxford University Press, ISBN 0-19-503965-3.
• О'Рурк, Джозеф ; Суповит, Кеннет Дж. (1983), «Некоторые NP-трудные проблемы разложения полигонов», IEEE Transactions on Information Theory , 29 (2): 181–190, doi :10.1109/TIT.1983.1056648, MR  0712374.
• Сак, Дж. Р .; Туссен, Г. Т. (1988), «Размещение защитных устройств в прямолинейных многоугольниках», в книге Туссен, Г. Т. (ред.), Computational Morphology , North-Holland, стр. 153–176.
• Шермер, Томас (1992), «Последние результаты в художественных галереях» (PDF) , Труды IEEE , 80 (9): 1384–1399, doi :10.1109/5.163407.
• Уррутия, Хорхе (2000), «Проблемы художественной галереи и освещения», в Sack, J. -R.; Уррутия, Хорхе (ред.), Handbook of Computational Geometry , North-Holland, стр. 973–1027, doi :10.1016/B978-044482537-7/50023-1, ISBN 978-0-444-82537-7.
• Вальтр, П. (1998), «Охрана галерей, где ни одна точка не видит малую область», Израильский журнал математики , 104 (1): 1–16, doi : 10.1007/BF02897056.