Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Два измерения [ править ]

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

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

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

Теорема Хватала о художественной галерее [ править ]

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

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

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

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

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

Сначала многоугольник триангулируется (без добавления дополнительных вершин). Вершины получившегося триангуляционного графа могут быть трехцветными . [a] Ясно, что при раскраске 3 каждый треугольник должен иметь все три цвета. Вершины любого одного цвета образуют допустимый защитный набор, потому что каждый треугольник многоугольника охраняется его вершиной этого цвета. Поскольку три цвета разделяют n вершин многоугольника, цвет с наименьшим количеством вершин определяет допустимый набор защит с не более, чем защитниками .

Обобщения [ править ]

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

Есть ряд других обобщений и специализаций исходной теоремы о художественной галерее. [6] Например, для ортогональных многоугольников , у которых края / стены пересекаются под прямым углом, необходимы только защитные ограждения. Есть по крайней мере три различных доказательства этого результата, ни одно из которых не является простым: Каном, Клаве и Клейтманом ; пользователя Lubiw ; и Сэком и Туссеном . [7] [8]

Связанная проблема требует, чтобы количество охранников покрыло внешнюю часть произвольного многоугольника («Проблема крепости»): иногда это необходимо и всегда достаточно. Другими словами, покрыть бесконечную внешность сложнее, чем ограниченную внутреннюю часть. [9]

Вычислительная сложность [ править ]

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

Что касается алгоритмов аппроксимации для минимального количества охранников, Eidenbenz, Stamm & Widmayer (2001) доказали, что проблема является APX-сложной, подразумевая, что маловероятно, что какой-либо коэффициент аппроксимации лучше, чем некоторая фиксированная константа, может быть достигнут с помощью алгоритма аппроксимации за полиномиальное время . Однако до недавнего времени не был известен алгоритм достижения постоянного отношения приближения. Ghosh (1987) показал, что логарифмическое приближение может быть достигнуто для минимального количества защитных элементов вершин путем дискретизации входного многоугольника на выпуклые подобласти и последующего сведения проблемы к задаче множества покрытий . Как Валтр (1998)Показано, что система множеств, полученная из задачи художественной галереи, имеет ограниченную размерность VC , что позволяет применять алгоритмы покрытия множеств, основанные на ε-сетях , коэффициент аппроксимации которых является логарифмом оптимального числа охранников, а не числа вершин многоугольника. [12] Для неограниченных охранников бесконечное количество потенциальных позиций охранников делает проблему еще более сложной. Однако, ограничивая ограждения на мелкой сетке, можно получить более сложный алгоритм логарифмического приближения при некоторых мягких дополнительных предположениях, как показано Bonnet & Miltzow (2017) . Однако известны эффективные алгоритмы для нахождения набора не болеевершинные охранники, соответствующие верхней границе Хватала. Дэвид Авис и Годфрид Туссент  ( 1981 ) доказали, что размещение этих охранников может быть вычислено за O (n log n) времени в худшем случае с помощью алгоритма «разделяй и властвуй» . Kooshesh & Moret (1992) дали алгоритм линейного времени , используя краткое доказательство Фиска и алгоритм триангуляции линейной плоскости времени Бернара Шазелла .

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

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

Три измерения [ править ]

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

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


Возможные сценарии использования проблемы художественной галереи

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

См. Также [ править ]

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

Заметки [ править ]

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

Ссылки [ править ]

  1. ↑ О'Рурк (1987) , стр. 1.
  2. ^ Chvátal (1975) .
  3. Перейти ↑ Fisk (1978) .
  4. Перейти ↑ Aigner & Ziegler (2018) .
  5. ↑ О'Рурк (1987) , стр. 13.
  6. ^ Шермер (1992) .
  7. ^ Кан, Клаве и Клейтман (1983) ; Любив (1985) ; Мешок и Туссен (1988) .
  8. ↑ О'Рурк (1987) , стр. 31–80.
  9. ^ О'Рурк (1987) , стр. 146-154.
  10. ^ Abrahamsen, Adamaszek & Мильцов (2018) .
  11. ^ О'Рурк & Supowit (1983) ; Ли и Лин (1986) .
  12. ^ Brönnimann & Гудрич (1995) .
  13. ^ Коуто де Rezende и де Соуза (2011) .
  14. ↑ О'Рурк (1987) , стр. 255.

Источники [ править ]

  • Абрахамсен, Миккель; Адамашек, Анна; Милцов, Тилльманн (2018), «Проблема художественной галереи - завершена», в Диакониколасе, Илиас; Кемпе, Дэвид; Хенцингер, Моника (ред.), Труды 50-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2018, Лос-Анджелес, Калифорния, США, 25–29 июня 2018 г. , ACM, стр. 65–73, arXiv : 1704.06969 , DOI : 10,1145 / 3188745,3188868 , МР 3826234 
  • Аггарвал А. (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 г., Revised Selected Papers , Lecture Notes in Computer Science, 11926 , Berlin: Springer, стр. 1 –17, DOI : 10.1007 / 978-3-030-39479-0_1.
  • Авис, Д .; Туссен, GT (1981), «Эффективный алгоритм разложения многоугольника на многоугольники в форме звезды» (PDF) , Распознавание образов , 13 (6): 395–398, DOI : 10.1016 / 0031-3203 (81) 90002-9.
  • Бхаттачарья, Притам; Гош, Субир Кумар; Пал, Судебкумар (2017), Алгоритмы постоянной аппроксимации для защиты простых многоугольников с использованием Vertex Guards , arXiv : 1712.05492
  • Бхаттачарья, Притам; Гош, Субир Кумар; Рой, Бодхаян (2017), "Аппроксимируемость защиты многоугольников слабой видимости", Дискретная прикладная математика , 228 : 109–129, arXiv : 1409.4621 , doi : 10.1016 / j.dam.2016.12.015 , MR  3662965
  • Бонне, Эдуард; Miltzow, Tillmann (2017), «Алгоритм приближения для задачи художественной галереи», в Аронов, Борис; Кац, Мэтью Дж. (Ред.), 33-й Международный симпозиум по вычислительной геометрии, SoCG 2017, 4-7 июля 2017 г., Брисбен, Австралия , LIPIcs, 77 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 20: 1– 20:15, Arxiv : +1607,05527 , DOI : 10,4230 / LIPIcs.SoCG.2017.20 , МР  3685692.
  • Brönnimann, H .; Гудрич МТ (1995), "Почти оптимальный набор крышка в конечной VC-размерности", Дискретная и вычислительная геометрия , 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 .; де Соуза, C. (2011), "Точный алгоритм минимизации вершинных стражников на художественных галереях", международные операции в операционных исследованиях , 18 (4): 425-448, DOI : 10.1111 / j.1475-3995.2011.00804.x.
  • de Rezende, P .; de Souza, C .; Couto, M .; Тозони, Д. (2011), "Проблема художественной галереи с Vertex Guards" , проект "Проблема художественной галереи" , Instituto de Computação.
  • Дешпанде, Аджай; Ким, Тэджунг; Демейн, Эрик Д .; Сарма, Санджай Э. (2007), "Псевдополиномиальный алгоритм приближения времени O (logn) для задач художественной галереи", Proc. Worksh. Алгоритмы и структуры данных , Lecture Notes в области компьютерных наук, 4619 , Springer-Verlag, стр 163-174,. Дои : 10.1007 / 978-3-540-73951-7_15 , ЛВП : 1721,1 / 36243 , ISBN 978-3-540-73948-7.
  • Eidenbenz, S .; Stamm, C .; Видмайер, П. (2001), «Результаты неприблизимости для защиты полигонов и территорий» (PDF) , Algorithmica , 31 (1): 79–113, doi : 10.1007 / s00453-001-0040-8 , заархивировано из оригинала (PDF ) на 24.06.2003 CS1 maint: discouraged parameter (link).
  • Фиск, С. (1978), «Краткое доказательство теоремы Хватала о сторожем», Журнал комбинаторной теории, серия B , 24 (3): 374, DOI : 10.1016 / 0095-8956 (78) 90059-X.
  • Гош, СК (1987), "Алгоритмы приближения для задач художественной галереи", Proc. Конгресс канадского общества обработки информации , стр. 429–434..
  • Kahn, J .; Клаве, М .; Клейтман, Д. (1983), «Традиционные галереи требуют меньше сторожа», SIAM J. Algebr. Дискретные методы , 4 (2): 194-206, DOI : 10,1137 / 0604020.
  • Кушеш А.А.; Морет, BME (1992), «Трехкратная раскраска вершин триангулированного простого многоугольника», Распознавание образов , 25 (4): 443, DOI : 10.1016 / 0031-3203 (92) 90093-X.
  • Крон, Эрик А .; Nilsson, Бенгт J. (2013), "Приближенное охрану монотонные и прямолинейные многоугольники", Algorithmica , 66 (3): 564-594, DOI : 10.1007 / s00453-012-9653-3 , ЛВП : 2043/11487 , МР  3044626.
  • Ли, Д.Т .; Lin, AK (1986), "Вычислительная сложность художественной галереи проблем", IEEE Transactions по теории информации , 32 (2): 276-282, DOI : 10,1109 / TIT.1986.1057165.
  • Любив, А. (1985), "Разложение многоугольных областей на выпуклые четырехугольники", Proc. Первый ACM симпозиум по вычислительной геометрии . С. 97-106, DOI : 10,1145 / 323233,323247 , ISBN 0-89791-163-6 CS1 maint: discouraged parameter (link).
  • О'Рурк, Джозеф (1987), Теоремы и алгоритмы художественной галереи , Oxford University Press, ISBN 0-19-503965-3.
  • О'Рурк, Джозеф ; Supowit, Кеннет Дж (1983), "Некоторые задачи NP-жесткие разложения полигона", IEEE Transactions по теории информации , 29 (2): 181-190, DOI : 10,1109 / TIT.1983.1056648 , МР  0712374.
  • Мешок-младший ; Туссент, Г.Т. (1988), «Размещение защиты в прямолинейных многоугольниках», в Туссенте, Г.Т. (ред.), Вычислительная морфология , Северная Голландия, стр. 153–176..
  • Shermer, Томас (1992), "Новые результаты в картинных галереях" (PDF) , Труды IEEE , 80 (9): 1384-1399, DOI : 10,1109 / 5,163407.
  • Валтр, П. (1998), "Охрана галерей, где нет точки обзора небольшой площади", Israel J. Math. , 104 (1): 1–16, DOI : 10.1007 / BF02897056.