Проблема с картинной галереей

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

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

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

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

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

Четыре стражника способны прикрыть эту галерею.

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

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

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

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

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

История

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

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

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

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

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

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

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

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

Обобщения

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

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

Связанная с этим проблема требует количества охранников, которые будут прикрывать внешнюю часть произвольного многоугольника («Проблема крепости»): $\lceil n/2\rceil$ иногда необходимы и всегда достаточны, если на границе многоугольника размещена охрана, при этом $\lceil n/3\rceil$ иногда необходимы и всегда достаточны, если охрана размещена где-нибудь за пределами многоугольника. Другими словами, бесконечную внешнюю сторону охватить сложнее, чем конечную внутреннюю часть.

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

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

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

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

Точный алгоритм был предложен Коуто, де Резенде и де Соуза (2011) для защиты вершин. Авторы провели обширные вычислительные эксперименты с несколькими классами многоугольников, показавшие, что оптимальные решения могут быть найдены за относительно небольшое время вычислений даже для случаев, связанных с тысячами вершин. Исходные данные и оптимальные решения для этих случаев доступны для скачивания.

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

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

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

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

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

См. также

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

Источники

• Абрахамсен, Миккель; Адамашек, Анна; Мильцов, Тильманн (2022), «Проблема художественной галереи заключается в том, что $\exists {\mathbb {R}}$-complete», Journal of the ACM , 69 (1): A4:1–A4:70, arXiv : 1704.06969 , doi : 10.1145/3486220 , MR   4402363 , S2CID   245059672
• Аггарвал, А. (1984), Теорема о художественной галерее: ее варианты, приложения и алгоритмические аспекты , доктор философии. диссертация, Университет Джонса Хопкинса .
• Айгнер, Мартин ; Циглер, Гюнтер М. (2018), «Глава 40: Как охранять музей», Доказательства из КНИГИ (6-е изд.), Берлин: Springer, стр. 281–283, doi : 10.1007/978-3-662- 57265-8 , ISBN  978-3-662-57264-1 , МР   3823190 .
• Ашур, Став; Фильцер, Омрит; Кац, Мэтью Дж.; Сабан, Рэйчел (2019), «Графы, подобные ландшафту: PTAS для защиты слабовидимых полигонов и ландшафтов», в Бамписе, Эврипидисе; Мегоу, Николь (ред.), Аппроксимация и онлайн-алгоритмы — 17-й международный семинар, WAOA 2019, Мюнхен, Германия, 12–13 сентября 2019 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 11926, Берлин: Springer, стр. 1–17, doi : 10.1007/978-3-030-39479-0_1 , ISBN.  978-3-030-39478-3 , S2CID   210936577 .
• Авис, Д .; Туссен, GT (1981), «Эффективный алгоритм разложения многоугольника на звездообразные многоугольники» (PDF) , Распознавание образов , 13 (6): 395–398, Бибкод : 1981PatRe..13..395A , doi : 10.1016 /0031-3203(81)90002-9 .
• Бхаттачарья, Притам; Гош, Субир Кумар; Пал, Судебкумар (2017), Алгоритмы постоянной аппроксимации для защиты простых многоугольников с использованием защиты вершин , arXiv : 1712.05492
• Бхаттачарья, Притам; Гош, Субир Кумар; Рой, Бодхаян (2017), «Аппроксимируемость защиты полигонов слабой видимости», Дискретная прикладная математика , 228 : 109–129, arXiv : 1409.4621 , doi : 10.1016/j.dam.2016.12.015 , MR   3662965 , S2CID   991 6523
• Бонне, Эдуард; Мильцов, Тильманн (2017), «Алгоритм аппроксимации проблемы художественной галереи», Аронов, Борис; Кац, Мэтью Дж. (ред.), 33-й Международный симпозиум по вычислительной геометрии, SoCG 2017, 4–7 июля 2017 г., Брисбен, Австралия , LIPics, vol. 77, Schloss Dagstuhl — Центр компьютерных наук Лейбница, стр. 20:1–20:15, arXiv : 1607.05527 , doi : 10.4230/LIPIcs.SoCG.2017.20 , MR   3685692 , S2CID   1293138 .
• Брённиманн, Х.; Гудрич, М.Т. (1995), «Почти оптимальное множество покрытий в конечной VC-размерности», Дискретная и вычислительная геометрия , 14 (1): 463–479, doi : 10.1007/BF02570718 .
• Хватал, В. (1975), «Комбинаторная теорема в плоской геометрии», Журнал комбинаторной теории, серия B , 18 : 39–41, doi : 10.1016/0095-8956(75)90061-1 .
• Коуто, М.; де Резенде, П.; де Соуза, К. (2011), «Точный алгоритм минимизации защиты вершин в художественных галереях», International Transactions in Operational Research , 18 (4): 425–448, doi : 10.1111/j.1475-3995.2011.00804.x .
• де Резенде, П.; де Соуза, К.; Коуто, М.; Тозони, Д. (2011), «Проблема художественной галереи с защитой вершин» , Проект проблемы художественной галереи , Институт вычислительной техники .
• Дешпанде, Аджай; Ким, Тэджон; Демейн, Эрик Д .; Сарма, Санджай Э. (2007), «Алгоритм O(logn)-аппроксимации псевдополиномиального времени для задач художественной галереи», Proc. Воркш. Алгоритмы и структуры данных , Конспекты лекций по информатике, вып. 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 .
• Эйденбенц, С.; Штамм, К.; Видмайер, П. (2001), «Результаты неаппроксимируемости для защиты полигонов и ландшафтов» (PDF) , Algorithmica , 31 (1): 79–113, doi : 10.1007/s00453-001-0040-8 , S2CID   14532511 , заархивировано из оригинал (PDF) от 24 июня 2003 г.
• Фиск, С. (1978), «Краткое доказательство теоремы Хваталя о стороже», Журнал комбинаторной теории, серия B , 24 (3): 374, doi : 10.1016/0095-8956(78)90059-X .
• Гош, С.К. (1987), "Алгоритмы аппроксимации задач художественной галереи", Proc. Конгресс Канадского общества обработки информации , стр. 429–434 .
• Кан, Дж.; Клаве, М. ; Клейтман, Д. (1983), «Традиционные галереи требуют меньше сторожей», SIAM J. Algebr. Дискретные методы , 4 (2): 194–206, doi : 10.1137/0604020 .
• Кушеш А.А.; Море, BME (1992), «Раскраска вершин простого треугольного многоугольника в три цвета», Распознавание образов , 25 (4): 443, Bibcode : 1992PatRe..25..443K , doi : 10.1016/0031-3203(92) 90093-Х .
• Крон, Эрик А.; Нильссон, Бенгт Дж. (2013), «Приблизительная защита монотонных и прямолинейных многоугольников» , Algorithmica , 66 (3): 564–594, doi : 10.1007/s00453-012-9653-3 , hdl : 2043/11487 , MR   3044626 , S2CID   1458082 .
• Ли, DT ; Лин, А.К. (1986), «Вычислительная сложность задач художественной галереи», IEEE Transactions on Information Theory , 32 (2): 276–282, doi : 10.1109/TIT.1986.1057165 .
• Любив А. (1985), «Разложение многоугольных областей на выпуклые четырехугольники», Proc. 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 .
• Сак, младший ; Туссен, GT (1988), «Размещение защиты в прямолинейных многоугольниках», в Туссен, GT (ред.), Вычислительная морфология , Северная Голландия, стр. 153–176 .
• Шермер, Томас (1992), «Последние результаты в художественных галереях» (PDF) , Proceedings of the IEEE , 80 (9): 1384–1399, doi : 10.1109/5.163407 .
• Уррутия, Хорхе (2000), «Художественная галерея и проблемы освещения», в Саке, Ж.-Р.; Уррутиа, Хорхе (ред.), Справочник по вычислительной геометрии , Северная Голландия, стр. 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 .