Полигональное покрытие - Polygon covering

А покрытие из многоугольник представляет собой набор примитивных единиц (например, квадратов), объединение которых равно многоугольнику. А задача покрытия многоугольника задача поиска покрытия с наименьшим числом элементов для данного многоугольника. Это важный класс проблем в вычислительная геометрия. Существует множество различных проблем покрытия многоугольника, в зависимости от типа покрываемого многоугольника и от типов единиц, разрешенных в покрытии. Пример проблемы покрытия многоугольника: с учетом прямолинейный многоугольник, найдите наименьший набор квадратов, объединение которых равно многоугольнику.

В некоторых сценариях требуется покрывать не весь многоугольник, а только его края (это называется покрытие края многоугольника) или его вершины (это называется покрытие вершин многоугольника).

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

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

Базовые концепты

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

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

А минимальное покрытие - покрытие, не содержащее никаких других покрытий (т.е. это локальный минимум).

А минимальное покрытие покрытие с наименьшим количеством единиц (т. е. глобальным минимумом). Каждое минимальное покрытие минимально, но не наоборот.

Покрытие прямоугольного многоугольника квадратами

А прямолинейный многоугольник всегда можно покрыть конечным числом квадратов.

Для многоугольников без дырок минимальное покрытие квадратами можно найти за время O (п), куда п - количество вершин многоугольника.[1] Алгоритм использует подход локальной оптимизации: он создает покрытие, итеративно выбирая максимальные квадраты, которые необходимы для покрытия (- содержат непокрытые точки, не покрытые другими максимальными квадратами), а затем удаляя из многоугольника точки, которые становятся ненужными (- ненужными для поддержка будущих квадратов). Вот упрощенный псевдокод алгоритма:

  • Пока многоугольник п не пусто:
    • Выберите квадрат продолжения s в п.
    • Если балкон из s еще не охвачено, тогда добавьте s к покрытию.
    • Убрать балкон из s из п.
    • Если то, что осталось от s является продолжателем с одной ручкой, затем удалите из п определенный прямоугольник, прилегающий к ручке, оставив достаточное безопасное расстояние для будущих квадратов.
Удаление дырок из прямолинейного многоугольника.png

Для многоугольников, которые могут содержать дыры, поиск минимума такого покрытия: NP-жесткий.[2] Эту резкую разницу между полигонами без дыр и обычными полигонами можно интуитивно объяснить на основе следующей аналогии между максимальными квадратами в прямолинейном многоугольнике и узлами в неориентированном графе:[1]

  • Некоторые максимальные квадраты имеют непрерывное пересечение с границей многоугольника; когда они удаляются, оставшийся многоугольник остается связанным. Такие квадраты называются «продолжателями» и аналогичны листовым узлам - узлам с одним ребром - которые можно удалить, не отключая граф.
  • Остальные максимальные квадраты являются «разделителями»: при их удалении многоугольник разбивается на два несвязных многоугольника. Они аналогичны узлам с двумя или более ребрами, которые при удалении оставляют несвязанный остаток.

В прямолинейном многоугольнике без дырок все максимальные квадраты являются либо продолжителями, либо разделителями; таким образом, такой многоугольник аналогичен древовидный граф. Общий многоугольник аналогичен общему графу. Как и Крышка Vertex проблема полиномиальна для древовидных графов, но NP-трудна для общих графов, проблема покрытия квадратов линейна для многоугольников без дырок, но NP-трудна для общих многоугольников.

Можно использовать линейный алгоритм для получения 2-аппроксимации, т. Е. Покрытия максимум с 2 atOPT квадратами, где OPT - количество квадратов в минимальном покрытии:[3]

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

Количество квадратов в получившемся покрытии не более OPT + HOLES, где HOLES - количество отверстий. Можно доказать, что OPT≥HOLES. Следовательно, количество квадратов в покрытии не превосходит 2⋅OPT.

Покрытие прямолинейного многоугольника прямоугольниками

Для обычных прямолинейных многоугольников проблема поиска минимального покрытия прямоугольника является NP-трудной, даже если целевой многоугольник не имеет отверстий.[4] Было предложено несколько частичных решений этой проблемы:

1. В ортогонально выпуклый многоугольников, количество прямоугольников в минимальном покрытии равно количеству блоков в анти прямоугольник, и этот факт можно использовать для построения алгоритма полиномиального времени для поиска минимального покрытия прямоугольниками.[5]

2. Даже если целевой многоугольник выпуклый только наполовину ортогонально (т.е. только в у направление) минимальное покрытие прямоугольниками можно найти за время O (п2), куда п - количество вершин многоугольника.[6]

3. Алгоритм аппроксимации, который дает хорошие эмпирические результаты на реальных данных, представлен.[7]

4. Для прямолинейных многоугольников, которые могут содержать дыры, есть O (√бревно п) факторный алгоритм аппроксимации.[8]

Покрытие прямолинейного многоугольника ортогонально выпуклыми многоугольниками

Для прямолинейный многоугольник который является полуортогонально выпуклым (т.е. только в Икс направление), минимальное покрытие ортогонально выпуклый полигоны можно найти за время O (п^ 2), где п - количество вершин многоугольника. То же верно и для покрытия прямолинейным звездные многоугольники.[9]

Количество ортогонально-выпуклых компонент в минимальном покрытии в некоторых случаях можно найти, не находя самого покрытия, за время O (п).[10]

Покрытие прямолинейного многоугольника звездчатыми многоугольниками

Прямолинейный звездный многоугольник многоугольник п содержащий точку п, так что для каждой точки q в п, существует ортогонально выпуклый многоугольник, содержащий п и q.

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

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

Покрытие многоугольника без острых углов квадратами или прямоугольниками

Самый общий класс многоугольников, для которых можно найти покрытия квадратами или прямоугольниками, - это класс многоугольников без острых внутренних углов. Это потому, что острый угол не может быть покрыт конечным числом прямоугольников. Эта задача является NP-сложной, но существует несколько алгоритмов аппроксимации.[12]

Покрытие многоугольника прямоугольниками конечного семейства

В некоторых случаях многоугольник необходимо покрыть не произвольными прямоугольниками, а прямоугольниками из конечного семейства.[13]

Покрытие многоугольника треугольниками

Найти наименьший набор треугольников, покрывающих данный многоугольник, NP-сложно. Это также трудно приблизить - каждый алгоритм с полиномиальным временем может найти покрытие размером (1 + 1/19151), умноженное на минимальное покрытие.[14]

Если многоугольник находится в общая позиция (т.е. никакие два ребра не лежат на одной прямой), то каждый треугольник может покрывать не более 3 ребер многоугольника. Следовательно, каждый Триангуляция многоугольника является 3-приближением.

Если покрытие ограничено треугольниками, вершины которых являются вершинами многоугольника (т.е. Очки Штайнера не допускаются), то проблема NP-полная.

Если очки Штейнера не разрешены и многоугольник находится в общая позиция (т.е. никакие два ребра не коллинеарны), то каждое минимальное покрытие без точек Штейнера также является минимальным разбиением многоугольника на треугольники (т.е. треугольники в минимальном покрытии не перекрываются).[14] Следовательно, задача минимального покрытия идентична задаче Триангуляция многоугольника задача, которую можно решить за время O (пбревноп). Обратите внимание: если мы откажемся от предположения об общем положении, останутся многоугольники, в которых треугольники оптимального покрытия перекрываются. Подумайте о Звезда Давида Например.

Задача покрытия треугольниками только границы многоугольника является NP-полной, но существует эффективная 2-аппроксимация.[14]

Покрытие многоугольника выпуклыми многоугольниками

Покрытие многоугольника (который может содержать дыры) выпуклыми многоугольниками NP-сложно.[15] Есть O (журналп) аппроксимационный алгоритм.[16]

Покрытие многоугольника выпуклыми многоугольниками NP-сложно, даже если целевой многоугольник без дыр.[4] Это также APX-жесткий.[16] Проблема является NP-полной, когда покрытие не должно вводить новые вершины (т.е. Очки Штайнера не допускаются).[14]

Покрытие многоугольника звездчатыми многоугольниками

Основная статья: Проблема с картинной галереей

Покрытие простого многоугольника звездчатыми многоугольниками -полный, как и версия, в которой точка ядра каждой звезды должна находиться на краю многоугольника.[17]

Другие комбинации

Покрытие многоугольника (который может содержать дыры) с помощью спирали NP-сложно.[15]

Покрытие многоугольника Псевдотреугольники также был изучен.

Дополнительную информацию можно найти в.[18]

Смотрите также

Рекомендации

  1. ^ а б Bar-Yehuda, R .; Бен-Ханох, Э. (1996). «Алгоритм линейного времени для покрытия простых многоугольников подобными прямоугольниками». Международный журнал вычислительной геометрии и приложений. 06: 79–102. Дои:10.1142 / S021819599600006X.
  2. ^ Aupperle, L.J .; Conn, H.E .; Keil, J.M .; О'Рурк, Джозеф (1988). «Покрытие ортогональных многоугольников квадратами». Proc. 26-я Allerton Conf. Commun. Control Comput.: 97–106.
  3. ^ Проф. Реувен Бар-Иегуда в личном общении
  4. ^ а б Culberson, J.C .; Рекхов, Р. А. (1988). «Покрытие полигонов сложно». [Proceedings 1988] 29-й ежегодный симпозиум по основам компьютерных наук. п. 601. Дои:10.1109 / sfcs.1988.21976. ISBN  978-0-8186-0877-3..
  5. ^ Chaiken, S .; Kleitman, D. J .; Сакс, М .; Ширер, Дж. (1981). «Покрытие областей прямоугольниками». Журнал SIAM по алгебраическим и дискретным методам. 2 (4): 394. Дои:10.1137/0602042.
  6. ^ Franzblau, D. S .; Клейтман Д. Дж. (1984). «Алгоритм построения областей с прямоугольниками». Материалы шестнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '84. п. 167. Дои:10.1145/800057.808678. ISBN  978-0897911337.
  7. ^ Генрих-Литан, Л .; Люббеке, М. Э. (2007). "Прямоугольные покрытия пересмотрены с помощью вычислений". Журнал экспериментальной алгоритмики. 11: 2.6. CiteSeerX  10.1.1.69.4576. Дои:10.1145/1187436.1216583.
  8. ^ Кумар, В. С. А .; Рамеш, Х. (2003). «Покрытие прямолинейных многоугольников прямоугольниками, параллельными осям». SIAM Журнал по вычислениям. 32 (6): 1509. CiteSeerX  10.1.1.20.2664. Дои:10.1137 / s0097539799358835.
  9. ^ Кейл, Дж. М. (1986). «Минимально покрывающий горизонтально выпуклый ортогональный многоугольник». Материалы второго ежегодного симпозиума по вычислительной геометрии - SCG '86. С. 43–51. Дои:10.1145/10515.10520. ISBN  978-0897911948.
  10. ^ Culberson, J .; Рекхов, Р. А. (1989). «Ортогонально выпуклые накрытия ортогональных многоугольников без дырок». Журнал компьютерных и системных наук. 39 (2): 166. Дои:10.1016/0022-0000(89)90043-3.
  11. ^ Motwani, R .; Рагхунатан, А .; Саран, Х. (1990). «Покрытие ортогональных многоугольников звездчатыми многоугольниками: подход идеального графа». Журнал компьютерных и системных наук. 40: 19–48. Дои:10.1016 / 0022-0000 (90) 90017-ф.
  12. ^ Levcopoulos, C .; Гудмундссон, Дж. (1997). «Аппроксимационные алгоритмы покрытия многоугольников квадратами и подобные задачи». Методы рандомизации и аппроксимации в компьютерных науках. Конспект лекций по информатике. 1269. п. 27. CiteSeerX  10.1.1.22.9094. Дои:10.1007/3-540-63248-4_3. ISBN  978-3-540-63248-1., Гражина Звозняк, 1998
  13. ^ Стоян, Ю.Г .; Романова, Т .; Scheithauer, G .; Кривуля, А. (2009). «Покрытие многоугольной области прямоугольниками». Вычислительная оптимизация и приложения. 48 (3): 675. Дои:10.1007 / s10589-009-9258-1.
  14. ^ а б c d Христос, Т. (2011). «За пределами триангуляции: покрытие многоугольников треугольниками». Алгоритмы и структуры данных. Конспект лекций по информатике. 6844. С. 231–242. Дои:10.1007/978-3-642-22300-6_20. ISBN  978-3-642-22299-3.
  15. ^ а б О'Рурк, Дж .; Суповит, К. (1983). «Некоторые NP-трудные задачи декомпозиции полигонов». IEEE Transactions по теории информации. 29 (2): 181. Дои:10.1109 / tit.1983.1056648.
  16. ^ а б Eidenbenz, S .; Видмайер, П. (2001). «Алгоритм аппроксимации минимального выпуклого покрытия с логарифмической гарантией качества». Алгоритмы - ESA 2001. Конспект лекций по информатике. 2161. п. 333. Дои:10.1007/3-540-44676-1_28. ISBN  978-3-540-42493-2.
  17. ^ Абрахамсен, Миккель; Адамашек, Анна; Мильцов, Тилльманн (2017), Проблема художественной галереи -полный, arXiv:1704.06969, Bibcode:2017arXiv170406969A
  18. ^ Кейл, Дж. М. (2000). «Разложение многоугольника». Справочник по вычислительной геометрии. С. 491–518. Дои:10.1016 / B978-044482537-7 / 50012-7. ISBN  9780444825377.