WikiSort.ru - Не сортированное

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

Теорема Шватала о картинной галерее (канадского математика, родившегося в Праге, Вацлава Шватала^[en]), даёт верхнюю границу минимального числа охранников. Теорема утверждает, что ${\displaystyle \left\lfloor n/3\right\rfloor }$ охранников всегда достаточно, а иногда и необходимо, чтобы охранять простой многоугольник с ${\displaystyle n}$ вершинами.

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

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

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

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

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

Обобщения

Верхняя граница Шватала остаётся верной, если охранники и не обязаны находиться в вершинах многоугольника (но должны быть внутри него).

Есть много других обобщений и конкретизаций исходной теоремы о галерее^[5]. Например, для ортогональных многоугольников^[en], в которых рёбра/стены находятся под прямыми углами, нужно только ${\displaystyle \lfloor n/4\rfloor }$ охранников. Существует по меньшей мере три различных доказательства этого результата, и ни одно из них не является простым, это доказательство Кана, Марии Клаве^[en] и Даниэля Клейтмана^[en][6], доказательство Анны Любив^[en][7] и доказательство Ёрга-Рюдигера Сака и Туссэна^[8][9].

Связанная задача спрашивает о числе охранников для перекрытия внешней области произвольного многоугольника ("Задача о крепости") — иногда необходимо иметь ${\displaystyle \lceil n/2\rceil }$ охранников и этого числа всегда достаточно. Другими словами, бесконечная внешняя область более сложна для охраны, чем конечная внутренняя область^[10].

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

В версиях задачи охраны галереи, поставленной как задача разрешимости, на входе задаётся как многоугольник, так и число k, результатом же решения задачи должен быть ответ, достаточно ли k охранников для охраны многоугольника. Эта задача и все её стандартные варианты (такие как ограничение размещения охранников в вершинах или на рёбрах многоугольника) являются NP-трудными^[11][12][13]. Для аппроксимационных алгоритмов задачи определения минимального числа охранников, Айденбенц, Штамм и Видмейер^[14] доказали, что задача APX-трудна, откуда следует, что вряд ли найдётся аппроксимационный алгоритм полиномиального времени с гарантированной эффективностью, лучшей, чем некоторая фиксированная константа. Однако константа гарантированной эффективности не известна. Может быть получена логарифмическая аппроксимация для минимального числа охранников в вершине путём сведения задачи к задаче задаче о покрытии множества^[15]. Как показал Вальтр^[16], задача о покрытии множеств, полученная из задачи о картинной галереи, имеет ограниченную размерность Вапника — Червоненкиса, что позволяет применение алгоритмов покрытия множеств, основанных на ε-сетях^[en], гарантированная эффективность которых логарифмически зависит от оптимального числа охранников, а не от числа вершин многоугольника^[17]. Когда размещение охранников не ограничивается, бесконечное число возможных положений охранников делает задачу ещё более сложной^[18].

Однако известны эффективные алгоритмы для поиска максимум ${\displaystyle \left\lfloor n/3\right\rfloor }$ охранников, расположенных в вершинах, что соответствует верхней границе Шватала. Дэвид Авис и Годфрид Туссэн^[19] доказали, что размещение охранников можно вычислить в худшем случае за время O(n log n) с помощью алгоритма «разделяй и властвуй». Кушеш и Морэ^[20] предложили алгоритм c линейным временем работы, в котором используется короткое доказательство Фиска и алгоритма плоской триангуляции Бернарда Шазелла с линейным временем работы.

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