Полигональное покрытие - Polygon covering
Покрытие из многоугольника представляет собой набор примитивных единиц (например , квадраты), объединение которых равно многоугольник. Полигона Задача о покрытии является проблема нахождения покрытие с наименьшим числом единиц для данного многоугольника. Это важный класс задач вычислительной геометрии . В зависимости от типа покрытия многоугольника возникает множество различных проблем с покрытием многоугольника. Пример проблемы покрытия многоугольника: для данного прямолинейного многоугольника найти наименьший набор квадратов, объединение которых равно многоугольнику.
В некоторых сценариях требуется покрывать не весь многоугольник, а только его ребра (это называется покрытием ребер многоугольника ) или его вершины (это называется покрытием вершин многоугольника ).
В задаче покрытия элементы покрытия могут перекрываться, если их объединение в точности равно целевому многоугольнику. Это контрастирует с проблемой упаковки , в которой единицы должны быть не пересекающимися, и их объединение может быть меньше, чем целевой многоугольник, и с проблемой разбиения многоугольника , в которой единицы должны быть не пересекающимися, а их объединение должно быть равно целевому. многоугольник.
Задача о многоугольном покрытии - это частный случай задачи о множественном покрытии . В общем, задача поиска наименьшего покрытия множества является NP-полной, но для специальных классов многоугольников требуется наименьшее время многоугольника.
Покрытие многоугольника Р представляет собой совокупность максимальных единиц, возможно перекрытие, объединение которых равен Р .
Минимальное покрытие является покрытием , которое не содержит какое - либо другое покрытия (т.е. локального минимума).
Минимальное покрытие является покрытием с наименьшим числом единиц (то есть глобальный минимум). Каждое минимальное покрытие минимально, но не наоборот.
Покрытие прямоугольного многоугольника квадратами
Прямолинейное полигон всегда можно покрыть конечным числом вершин многоугольника. Алгоритм использует подход локальной оптимизации: он строит покрытие, итеративно выбирая максимальные квадраты, которые необходимы для покрытия (- содержат непокрытые точки, не покрытые другими максимальными квадратами), а затем удаляя из многоугольника точки, которые становятся ненужными (- ненужными для поддержка будущих квадратов). Вот упрощенный псевдокод алгоритма:
- Пока многоугольник P не пустой:
- Выберите продолжателем квадрат S в P .
- Если балкон из й еще не покрыт, а затем добавить S к покрытию.
- Снимите балкон с с P .
- Если то, что осталось от s, - это продолжитель с одной ручкой, то удалите из P некоторый прямоугольник, примыкающий к ручке, стараясь оставить достаточное безопасное расстояние для будущих квадратов.
Для многоугольников, которые могут содержать дыры, найти минимум такого покрытия NP-сложно . Это резкое различие между полигонами без дыр и обычными полигонами может быть интуитивно объяснено на основе следующей аналогии между максимальными квадратами в прямолинейном многоугольнике и узлами в неориентированном графе:
- Некоторые максимальные квадраты имеют непрерывное пересечение с границей многоугольника; когда они удаляются, оставшийся многоугольник остается соединенным. Такие квадраты называются «продолжателями» и аналогичны листовым узлам - узлам с одним ребром, - которые можно удалить, не отключая граф.
- Остальные максимальные квадраты являются «разделителями»: при их удалении многоугольник разбивается на два несвязных многоугольника. Они аналогичны узлам с двумя или более ребрами, которые при удалении оставляют несвязанный остаток.
В прямолинейном многоугольнике без дырок все максимальные квадраты являются либо продолжителями, либо разделителями; таким образом, такой многоугольник аналогичен древовидному графу . Общий многоугольник аналогичен общему графу. Так же, как проблема вершинного покрытия является полиномиальной для древовидных графов, но NP-трудной для общих графов, проблема квадратного покрытия является линейной для многоугольников без дырок, но NP-трудной для общих многоугольников.
Можно использовать линейный алгоритм для получения 2-аппроксимации, т. Е. Покрытия с не более чем 2⋅OPT квадратами, где OPT - количество квадратов в минимальном покрытии:
- Для каждого отверстия найдите квадрат s, соединяющий отверстие с внешней границей.
- Вырежьте s из многоугольника, затем приклейте обратно две перекрывающиеся копии s (см. Рисунок). Полученный многоугольник не плоский, но все еще двумерный, и теперь в нем нет отверстий.
- Теперь воспользуйтесь исходным алгоритмом, чтобы найти минимальное покрытие.
Количество квадратов в получившемся покрытии не превосходит OPT + HOLES, где HOLES - количество отверстий. Можно доказать, что OPT≥HOLES. Следовательно, количество квадратов в покрытии не превосходит 2⋅OPT.
Покрытие прямолинейного многоугольника прямоугольниками
Для обычных прямолинейных многоугольников проблема поиска минимального покрытия прямоугольника является NP-трудной, даже если целевой многоугольник не имеет отверстий. Было предложено несколько частичных решений этой проблемы:
1. В ортогонально выпуклых многоугольниках количество прямоугольников в минимальном покрытии равно количеству блоков в антипрямоугольнике , и этот факт можно использовать для построения алгоритма полиномиального времени для поиска минимального покрытия прямоугольниками.
2. Даже когда целевой многоугольник выпуклый только наполовину ортогонально (то есть только в направлении y ), минимальное покрытие прямоугольниками может быть найдено за время O ( n 2 ), где n - количество вершин многоугольника.
3. Алгоритм аппроксимации, дающий хорошие эмпирические результаты на реальных данных, представлен в виде.
4. Для прямолинейных многоугольников, которые могут содержать дыры, существует алгоритм аппроксимации множителя O ( √ log n ).
Покрытие прямолинейного многоугольника ортогонально выпуклыми многоугольниками
Для прямолинейного многоугольника, который является полуортогонально выпуклым (т.е. только в направлении x ), минимальное покрытие ортогонально выпуклыми многоугольниками может быть найдено за время O ( n ^ 2), где n - количество вершин многоугольника. То же верно и для покрытия прямолинейными звездчатыми многоугольниками .
Количество ортогонально-выпуклых компонент в минимальном покрытии в некоторых случаях можно найти, не находя самого покрытия, за время O ( n ).
Покрытие прямолинейного многоугольника звездчатыми многоугольниками
Прямолинейный звездообразный многоугольник - это многоугольник P, содержащий точку p , такой, что для каждой точки q в P существует ортогонально выпуклый многоугольник, содержащий p и q .
Задача покрытия многоугольника звездчатыми многоугольниками - это вариант задачи картинной галереи .
Граф видимости для задачи минимального покрытия прямолинейных многоугольников без дырок звездчатыми многоугольниками представляет собой идеальный граф . Это свойство совершенства подразумевает полиномиальный алгоритм поиска минимального покрытия любого прямолинейного многоугольника прямолинейными звездчатыми многоугольниками.
Покрытие многоугольника без острых углов квадратами или прямоугольниками
Самый общий класс многоугольников, для которых могут быть найдены покрытия квадратами или прямоугольниками, - это класс многоугольников без острых внутренних углов. Это потому, что острый угол не может быть покрыт конечным числом прямоугольников. Эта задача является NP-сложной, но существует несколько алгоритмов аппроксимации.
Покрытие многоугольника прямоугольниками конечного семейства
В некоторых случаях многоугольник должен быть покрыт не произвольными прямоугольниками, а прямоугольниками из конечного семейства.
Покрытие многоугольника треугольниками
Найти наименьший набор треугольников, покрывающих данный многоугольник, NP-сложно. Это также трудно приблизить - каждый алгоритм с полиномиальным временем может найти покрытие размером (1 + 1/19151), умноженное на минимальное покрытие.
Если многоугольник находится в общем положении (т.е. никакие два ребра не коллинеарны), то каждый треугольник может покрывать не более 3 ребер многоугольника. Следовательно, любая триангуляция многоугольника является 3-приближением.
Если покрытие ограничено треугольниками, вершины которых являются вершинами многоугольника (т.е. точки Штейнера не допускаются), то проблема NP-полная.
Если точки Штейнера недопустимы и многоугольник находится в общем положении (т. Е. Никакие два ребра не коллинеарны), то каждое минимальное покрытие без точек Штейнера также является минимальным разбиением многоугольника на треугольники (т. Е. Треугольники в минимальном покрытии не должны перекрывать). Следовательно, задача минимального покрытия идентична задаче триангуляции многоугольника , которая может быть решена за время O ( n log n ). Обратите внимание, что если мы откажемся от предположения об общем положении, будут многоугольники, в которых треугольники в оптимальном покрытии перекрываются. Подумайте, например, о Звезде Давида .
Задача покрытия треугольниками только границы многоугольника является NP-полной, но существует эффективное 2-приближение.
Покрытие многоугольника выпуклыми многоугольниками
Покрытие многоугольника (который может содержать дыры) выпуклыми многоугольниками NP-сложно. Существует алгоритм приближения O (log n ).
Покрытие многоугольника выпуклыми многоугольниками NP-сложно, даже если целевой многоугольник не имеет отверстий . Это также APX-сложно . Проблема является NP-полной, когда покрытие не должно вводить новые вершины (т.е. точки Штейнера не допускаются).
Покрытие многоугольника звездчатыми многоугольниками
Покрытие простого многоугольника звездными многоугольниками является полным , как и версия, в которой точка ядра каждой звезды должна находиться на краю многоугольника.
Покрытие множества точек одинаковыми квадратами
Учитывая множество S точек на плоскости, и множество одинаковых квадратов, цель состоит в том, чтобы найти наименьшее число квадратов , которые могут охватывать все точки S .
Предположим, что для каждой точки p в S мы помещаем квадрат с центром в p . Пусть G S - граф пересечений этих квадратов. Обратите внимание, что две точки в S могут быть покрыты одним квадратом тогда и только тогда, когда два квадрата с центром в них перекрываются. Таким образом, квадрат-покрытие из точек в S эквивалентно кликой -накрывающей из G S . Найти наименьшее квадратное покрытие S NP-сложно; Доказательство - сокращение от 3SAT .
Другие комбинации
Покрытие многоугольника (который может содержать дыры) спиралями NP-сложно.
Также изучалось покрытие многоугольника псевдотреугольниками .
Дополнительную информацию можно найти в.