Задача о картинной галерее

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

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

Двумерное пространство

[править | править код]
Четыре камеры перекрывают эту галерею (камеры имеют обзор 360 градусов).

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

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

Теорема Хватала о картинной галерее

[править | править код]

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

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

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

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

Доказательство Стива Фиска[3] настолько коротко и элегантно, что приведено в книге «Доказательства из Книги».

Доказательство:

Триангулируем многоугольник без добавления вершин.

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

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

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

[править | править код]

В версиях задачи охраны галереи, поставленной как задача разрешимости, на входе задаётся как многоугольник, так и число k, результатом же решения задачи должен быть ответ, достаточно ли k охранников для охраны многоугольника. Эта задача и все её стандартные варианты (такие как ограничение размещения охранников в вершинах или на рёбрах многоугольника) являются NP-трудными[5][6][7]. Для аппроксимационных алгоритмов задачи определения минимального числа охранников, Айденбенц, Штамм и Видмейер[8] доказали, что задача APX-трудна, откуда следует, что вряд ли найдётся аппроксимационный алгоритм полиномиального времени с гарантированной эффективностью, лучшей, чем некоторая фиксированная константа. Однако константа гарантированной эффективности не известна. Может быть получена логарифмическая аппроксимация для минимального числа охранников в вершине путём сведения задачи к задаче задаче о покрытии множества[9]. Как показал Вальтр[10], задача о покрытии множеств, полученная из задачи о картинной галереи, имеет ограниченную размерность Вапника — Червоненкиса, что позволяет применение алгоритмов покрытия множеств, основанных на ε-сетях[англ.], гарантированная эффективность которых логарифмически зависит от оптимального числа охранников, а не от числа вершин многоугольника[11]. Когда размещение охранников не ограничивается, бесконечное число возможных положений охранников делает задачу ещё более сложной[12].

Однако известны эффективные алгоритмы для поиска максимум охранников, расположенных в вершинах, что соответствует верхней границе Хватала. Дэвид Авис и Годфрид Туссэн[13] доказали, что размещение охранников можно вычислить в худшем случае за время O(n log n) с помощью алгоритма «разделяй и властвуй». Кушеш и Морэ[14] предложили алгоритм c линейным временем работы, в котором используется короткое доказательство Фиска и алгоритма плоской триангуляции Бернарда Шазелла с линейным временем работы.

Точный алгоритм для охранников в вершинах предложили Коуту, де Резенде, де Соуза. Авторы провели интенсивные вычислительные эксперименты на некоторых классах многоугольников, которые показали, что оптимальные решения могут быть найдены за относительно малое вычислительное время даже для задач с тысячами вершин. Входные данные и оптимальные решения этих задач доступны для скачивания[15].

Вариации и обобщения

[править | править код]

Есть много других обобщений и конкретизаций исходной теоремы о галерее[16]. Например, для ортогональных многоугольников[англ.], в которых рёбра/стены находятся под прямыми углами, нужно только охранников. Существует по меньшей мере три различных доказательства этого результата, и ни одно из них не является простым, это доказательство Кана, Марии Клаве[англ.] и Даниэля Клейтмана[англ.][17], доказательство Анны Любив[англ.][18] и доказательство Ёрга-Рюдигера Сака и Туссэна[19][20].

Связанная задача спрашивает о числе охранников для перекрытия внешней области произвольного многоугольника ("Задача о крепости") — иногда необходимо иметь охранников и этого числа всегда достаточно. Другими словами, бесконечная внешняя область более сложна для охраны, чем конечная внутренняя область[21].

Трёхмерный случай

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

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

Примечания

[править | править код]

Литература

[править | править код]
  • М. Айглер, Г. Циглер. Доказательство из Книги. Лучшие доказательства сов времён Евклида до наших дней.. — Москва: «Мир», 2006. — ISBN 5-03-003690-3 УДК 51.1 ББК 22.1.
  • A. Aggarwal. The art gallery theorem: Its variations, applications, and algorithmic aspects. — Ph.D. thesis, Johns Hopkins University, 1984.
  • D. Avis, G. T. Toussaint. An efficient algorithm for decomposing a polygon into star-shaped polygons // Pattern Recognition. — 1981. — Т. 13, вып. 6. — С. 395–398. — doi:10.1016/0031-3203(81)90002-9.
  • H. Brönnimann, M. T. Goodrich. Almost optimal set covers in finite VC-dimension // Discrete and Computational Geometry. — 1995. — Т. 14. — С. 463–479. — doi:10.1007/BF02570718.
  • V. Chvátal. A combinatorial theorem in plane geometry // Journal of Combinatorial Theory, Series B. — 1975. — Т. 18. — С. 39–41. — doi:10.1016/0095-8956(75)90061-1.
  • M. Couto, P. de Rezende, C. de Souza. An exact algorithm for minimizing vertex guards on art galleries // International Transactions in Operational Research. — 2011. — doi:10.1111/j.1475-3995.2011.00804.x.
  • M. Couto, P. de Rezende, C. de Souza. Benchmark instances for the art gallery problem with vertex guards. — 2011.
  • Ajay Deshpande, Taejung Kim, Erik D. Demaine, Sanjay E. Sarma. A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems // Proc. Worksh. Algorithms and Data Structures. — Springer-Verlag, 2007. — Т. 4619. — С. 163–174. — (Lecture Notes in Computer Science). — ISBN 978-3-540-73948-7. — doi:10.1007/978-3-540-73951-7_15.
  • S. Eidenbenz, C. Stamm, P. Widmayer. Inapproximability results for guarding polygons and terrains // Algorithmica. — 2001. — Т. 31, вып. 1. — С. 79–113. — doi:10.1007/s00453-001-0040-8. Архивировано 24 июня 2003 года.
  • S. Fisk. A short proof of Chvátal's watchman theorem // Journal of Combinatorial Theory, Series B. — 1978. — Т. 24, вып. 3. — С. 374. — doi:10.1016/0095-8956(78)90059-X.
  • S. K. Ghosh. Proc. Canadian Information Processing Society Congress. — 1987. — С. 429–434.
  • J. Kahn, M. Klawe, D. Kleitman. Traditional galleries require fewer watchmen // SIAM J. Alg. Disc. Meth.. — 1983. — Т. 4, вып. 2. — С. 194–206. — doi:10.1137/0604020.
  • A. A. Kooshesh, B. M. E. Moret. Three-coloring the vertices of a triangulated simple polygon // Pattern Recognition. — 1992. — Т. 25, вып. 4. — С. 443. — doi:10.1016/0031-3203(92)90093-X.
  • D. T. Lee, A. K. Lin. Computational complexity of art gallery problems // IEEE Transactions on Information Theory. — 1986. — Т. 32, вып. 2. — С. 276–282. — doi:10.1109/TIT.1986.1057165.
  • A. Lubiw. Decomposing polygonal regions into convex quadrilaterals // Proc. 1st ACM Symposium on Computational Geometry. — 1985. — С. 97–106. — ISBN 0-89791-163-6. — doi:10.1145/323233.323247.
  • Joseph O'Rourke. Art Gallery Theorems and Algorithms. — Oxford University Press, 1987. — ISBN 0-19-503965-3.
  • J. R. Sack, G. T. Toussaint. Guard placement in rectilinear polygons // Computational Morphology / Toussaint G. T.. — North-Holland, 1988. — С. 153–176.
  • Thomas Shermer. Recent Results in Art Galleries // Proceedings of the IEEE. — 1992. — Т. 80, вып. 9. — С. 1384–1399. — doi:10.1109/5.163407.
  • P. Valtr. Guarding galleries where no point sees a small area // Israel J. Math.. — 1998. — Т. 104, вып. 1. — С. 1–16. — doi:10.1007/BF02897056.