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

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

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

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

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

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

Минимальным покрытием называется покрытие, не содержащее других покрытий (т. е. являющееся локальным минимумом).

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

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

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

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

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

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

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

Для получения 2-приближения можно использовать линейный алгоритм; т. е. покрытие не более чем с двумя квадратами opt , где opt — количество квадратов в минимальном покрытии: ^[3]

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

Число квадратов в полученном покрытии не превышает opt + holes , гдеholes — количество дырок. Можно доказать, что opt ≥ дырок . Следовательно, число квадратов в покрытии не превосходит 2 opt .

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

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

В ортогонально-выпуклых многоугольниках количество прямоугольников в минимальном покрытии равно количеству блоков в антипрямоугольнике , и этот факт можно использовать для построения полиномиального по времени алгоритма поиска минимального покрытия прямоугольниками. ^[5]
Даже если целевой многоугольник выпуклый только наполовину (т.е. только в направлении y ), минимальное покрытие прямоугольниками можно найти за время O( n ²), где n — количество вершин многоугольника. ^[6]
Алгоритм аппроксимации, который дает хорошие эмпирические результаты на реальных данных, представлен. ^[7]
Для прямолинейных многоугольников, которые могут содержать дыры, существует алгоритм аппроксимации коэффициента O( √ log n ). ^[8]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Покрытие многоугольника (который может содержать дыры) выпуклыми многоугольниками является NP-трудным. ^[15] Также было показано, что $\exists \mathbb {R}$ -полный. ^[16] Существует алгоритм аппроксимации O(log n ). ^[17]

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

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

Покрытие простого многоугольника звездчатыми многоугольниками $\exists \mathbb {R}$ -complete , как и версия, в которой точка ядра каждой звезды должна находиться на ребре многоугольника. ^[19]

Покрытие множества точек одинаковыми квадратами

Учитывая набор S точек на плоскости и набор одинаковых квадратов, цель состоит в том, чтобы найти наименьшее количество квадратов, которое может покрыть все точки в S .

Предположим, что для каждой точки p в S мы поместили квадрат с центром в p . Пусть GS _— граф пересечений этих квадратов. Обратите внимание, что две точки в S могут быть покрыты одним квадратом тогда и только тогда, когда два квадрата с центрами в них перекрываются. точек из S эквивалентно кликовому покрытию GS покрытие _{Следовательно, квадратное} . Найти наименьшее квадратное покрытие S NP-трудно; доказательство проводится путем сокращения из 3SAT . ^[20]

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

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

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

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

См. также

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Бар-Иегуда, Р.; Бен-Ханох, Э. (1996). «Алгоритм линейного времени для покрытия простых многоугольников подобными прямоугольниками». Международный журнал вычислительной геометрии и приложений . 06 :79–102. дои : 10.1142/S021819599600006X .
^ Опперле, LJ; Конн, HE; Кейл, Дж. М.; О'Рурк, Джозеф (1988). «Покрытие ортогональных многоугольников квадратами». Учеб. 26-я Аллертонская конференция. Коммун. Управляющий компьютер. : 97–106.
↑ Профессор Реувен Бар-Иегуда в личном общении.
^ Jump up to: Перейти обратно: ^а ^б Калберсон, Дж. К.; Рекхау, РА (1988). «Покрывать полигоны сложно». [Труды 1988 г.] 29-й ежегодный симпозиум по основам информатики . п. 601. дои : 10.1109/sfcs.1988.21976 . ISBN 978-0-8186-0877-3 . S2CID 34508387 . .
^ Чайкен, С.; Клейтман, диджей; Сакс, М.; Ширер, Дж. (1981). «Покрытие областей прямоугольниками». SIAM Journal по алгебраическим и дискретным методам . 2 (4): 394. дои : 10.1137/0602042 .
^ Францблау, Д.С.; Клейтман, диджей (1984). «Алгоритм построения областей из прямоугольников». Материалы шестнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '84 . п. 167. дои : 10.1145/800057.808678 . ISBN 978-0897911337 .
^ Генрих-Литан, Л.; Люббекке, Мэн (2007). «Прямоугольные покрытия, пересмотренные в вычислительном отношении». Журнал экспериментальной алгоритмики . 11 : 2.6. CiteSeerX 10.1.1.69.4576 . дои : 10.1145/1187436.1216583 . S2CID 619557 .
^ Кумар, ВСА; Рамеш, Х. (2003). «Покрытие прямолинейных многоугольников прямоугольниками, параллельными осям». SIAM Journal по вычислительной технике . 32 (6): 1509. CiteSeerX 10.1.1.20.2664 . дои : 10.1137/s0097539799358835 .
^ Кейл, Дж. М. (1986). «Минимальное покрытие горизонтально-выпуклого ортогонального многоугольника». Материалы второго ежегодного симпозиума по вычислительной геометрии - SCG '86 . стр. 43–51. дои : 10.1145/10515.10520 . ISBN 978-0897911948 .
^ Калберсон, Дж.; Рекхау, РА (1989). «Ортогонально-выпуклые покрытия ортогональных многоугольников без дырок» . Журнал компьютерных и системных наук . 39 (2): 166. дои : 10.1016/0022-0000(89)90043-3 .
^ Мотвани, Р.; Рагунатан, А.; Саран, Х. (1990). «Покрытие ортогональных многоугольников звездчатыми многоугольниками: идеальный графический подход» . Журнал компьютерных и системных наук . 40 : 19–48. дои : 10.1016/0022-0000(90)90017-ф .
^ Левкопулос, К.; Гудмундссон, Дж. (1997). «Аппроксимационные алгоритмы покрытия многоугольников квадратами и подобные задачи». Методы рандомизации и аппроксимации в информатике . Конспекты лекций по информатике. Том. 1269. с. 27. CiteSeerX 10.1.1.22.9094 . дои : 10.1007/3-540-63248-4_3 . ISBN 978-3-540-63248-1 . , Гражина Звозняк, 1998 г.
^ Стоян, Ю.Г.; Романова Т.; Шайтауэр, Г.; Кривуля, А. (2009). «Покрытие многоугольной области прямоугольниками». Вычислительная оптимизация и приложения . 48 (3): 675. doi : 10.1007/s10589-009-9258-1 . S2CID 15599243 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Христос, Т. (2011). «За пределами триангуляции: покрытие многоугольников треугольниками». Алгоритмы и структуры данных . Конспекты лекций по информатике. Том. 6844. стр. 231–242. дои : 10.1007/978-3-642-22300-6_20 . ISBN 978-3-642-22299-3 .
^ Jump up to: Перейти обратно: ^а ^б О'Рурк, Дж.; Суповит, К. (1983). «Некоторые NP-сложные задачи разложения многоугольников». Транзакции IEEE по теории информации . 29 (2): 181. doi : 10.1109/tit.1983.1056648 .
^ Абрахамсен, Миккель. «Покрывать полигоны еще сложнее» (PDF) . IEEE-FOCS .
^ Jump up to: Перейти обратно: ^а ^б Эйденбенц, С.; Видмайер, П. (2001). «Алгоритм аппроксимации минимального выпуклого покрытия с логарифмической гарантией производительности». Алгоритмы — ЕКА 2001 . Конспекты лекций по информатике. Том. 2161. с. 333. дои : 10.1007/3-540-44676-1_28 . ISBN 978-3-540-42493-2 .
^ «Программа – ФОКС 2023» . ОГОНЬ 2023 . IEEE.
^ Абрахамсен, Миккель; Адамашек, Анна; Мильцов, Тильманн (2017), Проблема художественной галереи: $\exists \mathbb {R}$ -complete , arXiv : 1704.06969 , Bibcode : 2017arXiv170406969A
^ Фаулер, Роберт Дж.; Патерсон, Майкл С.; Танимото, Стивен Л. (13 июня 1981 г.). «Оптимальная упаковка и покрытие в плоскости NP-полны» . Письма об обработке информации . 12 (3): 133–137. дои : 10.1016/0020-0190(81)90111-3 . ISSN 0020-0190 .
^ Кейл, Дж. М. (2000). «Разложение полигонов». Справочник по вычислительной геометрии . стр. 491–518. дои : 10.1016/B978-044482537-7/50012-7 . ISBN 9780444825377 .

[bybc96-1] Jump up to: Перейти обратно: ^а ^б Бар-Иегуда, Р.; Бен-Ханох, Э. (1996). «Алгоритм линейного времени для покрытия простых многоугольников подобными прямоугольниками». Международный журнал вычислительной геометрии и приложений . 06 :79–102. дои : 10.1142/S021819599600006X .

[acko88-2] Опперле, LJ; Конн, HE; Кейл, Дж. М.; О'Рурк, Джозеф (1988). «Покрытие ортогональных многоугольников квадратами». Учеб. 26-я Аллертонская конференция. Коммун. Управляющий компьютер. : 97–106.

[3] Профессор Реувен Бар-Иегуда в личном общении.

[cr88-4] Jump up to: Перейти обратно: ^а ^б Калберсон, Дж. К.; Рекхау, РА (1988). «Покрывать полигоны сложно». [Труды 1988 г.] 29-й ежегодный симпозиум по основам информатики . п. 601. дои : 10.1109/sfcs.1988.21976 . ISBN 978-0-8186-0877-3 . S2CID 34508387 . .

[5] Чайкен, С.; Клейтман, диджей; Сакс, М.; Ширер, Дж. (1981). «Покрытие областей прямоугольниками». SIAM Journal по алгебраическим и дискретным методам . 2 (4): 394. дои : 10.1137/0602042 .

[6] Францблау, Д.С.; Клейтман, диджей (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 . S2CID 619557 .

[8] Кумар, ВСА; Рамеш, Х. (2003). «Покрытие прямолинейных многоугольников прямоугольниками, параллельными осям». SIAM Journal по вычислительной технике . 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] Калберсон, Дж.; Рекхау, РА (1989). «Ортогонально-выпуклые покрытия ортогональных многоугольников без дырок» . Журнал компьютерных и системных наук . 39 (2): 166. дои : 10.1016/0022-0000(89)90043-3 .

[11] Мотвани, Р.; Рагунатан, А.; Саран, Х. (1990). «Покрытие ортогональных многоугольников звездчатыми многоугольниками: идеальный графический подход» . Журнал компьютерных и системных наук . 40 : 19–48. дои : 10.1016/0022-0000(90)90017-ф .

[12] Левкопулос, К.; Гудмундссон, Дж. (1997). «Аппроксимационные алгоритмы покрытия многоугольников квадратами и подобные задачи». Методы рандомизации и аппроксимации в информатике . Конспекты лекций по информатике. Том. 1269. с. 27. CiteSeerX 10.1.1.22.9094 . дои : 10.1007/3-540-63248-4_3 . ISBN 978-3-540-63248-1 . , Гражина Звозняк, 1998 г.

[13] Стоян, Ю.Г.; Романова Т.; Шайтауэр, Г.; Кривуля, А. (2009). «Покрытие многоугольной области прямоугольниками». Вычислительная оптимизация и приложения . 48 (3): 675. doi : 10.1007/s10589-009-9258-1 . S2CID 15599243 .

[c11-14] Jump up to: Перейти обратно: ^а ^б ^с ^д Христос, Т. (2011). «За пределами триангуляции: покрытие многоугольников треугольниками». Алгоритмы и структуры данных . Конспекты лекций по информатике. Том. 6844. стр. 231–242. дои : 10.1007/978-3-642-22300-6_20 . ISBN 978-3-642-22299-3 .

[os83-15] Jump up to: Перейти обратно: ^а ^б О'Рурк, Дж.; Суповит, К. (1983). «Некоторые NP-сложные задачи разложения многоугольников». Транзакции IEEE по теории информации . 29 (2): 181. doi : 10.1109/tit.1983.1056648 .

[16] Абрахамсен, Миккель. «Покрывать полигоны еще сложнее» (PDF) . IEEE-FOCS .

[ew01-17] Jump up to: Перейти обратно: ^а ^б Эйденбенц, С.; Видмайер, П. (2001). «Алгоритм аппроксимации минимального выпуклого покрытия с логарифмической гарантией производительности». Алгоритмы — ЕКА 2001 . Конспекты лекций по информатике. Том. 2161. с. 333. дои : 10.1007/3-540-44676-1_28 . ISBN 978-3-540-42493-2 .

[18] «Программа – ФОКС 2023» . ОГОНЬ 2023 . IEEE.

[19] Абрахамсен, Миккель; Адамашек, Анна; Мильцов, Тильманн (2017), Проблема художественной галереи: $\exists \mathbb {R}$ -complete , arXiv : 1704.06969 , Bibcode : 2017arXiv170406969A

[20] Фаулер, Роберт Дж.; Патерсон, Майкл С.; Танимото, Стивен Л. (13 июня 1981 г.). «Оптимальная упаковка и покрытие в плоскости NP-полны» . Письма об обработке информации . 12 (3): 133–137. дои : 10.1016/0020-0190(81)90111-3 . ISSN 0020-0190 .

[21] Кейл, Дж. М. (2000). «Разложение полигонов». Справочник по вычислительной геометрии . стр. 491–518. дои : 10.1016/B978-044482537-7/50012-7 . ISBN 9780444825377 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]