Геометрическая задача о покрытии множества

Задача покрытия геометрического множества является частным случаем задачи покрытия множества в геометрических настройках. Входными данными является пространство диапазонов , где есть вселенная точек в и есть семейство подмножеств называемых диапазонов , определяемых пересечением и геометрических фигур, таких как диски и прямоугольники с параллельными осями. Цель состоит в том, чтобы выбрать подмножество диапазонов минимального размера таким образом, чтобы каждая точка во вселенной была покрыта некоторым диапазоном в . ${\displaystyle \Sigma =(X,{\mathcal {R}})}$ ${\displaystyle X}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {C}}\subseteq {\mathcal {R}}}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {C}}}$

При наличии того же пространства диапазонов тесно связанной задачей является геометрическая задача попадания в множество , где целью является выбор подмножества точек минимального размера , такого, чтобы каждый диапазон имел непустое пересечение с , т. е. попадал в . ${\displaystyle \Sigma }$ ${\displaystyle H\subseteq X}$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle H}$ ${\displaystyle H}$

В одномерном случае, когда содержит точки на действительной прямой и определяется интервалами, обе задачи — геометрическое покрытие множества и попадание в множество — могут быть решены за полиномиальное время с помощью простого жадного алгоритма . Однако в более высоких размерностях они, как известно, являются NP-полными даже для простых форм, т. е. когда индуцируется единичными дисками или единичными квадратами. ^[1] Задача покрытия дискретного единичного диска является геометрической версией общей задачи покрытия множества, которая является NP-трудной . ^[2] ${\displaystyle X}$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle {\mathcal {R}}}$

Для этих задач было разработано множество алгоритмов приближения . Благодаря геометрической природе, коэффициенты приближения для этих задач могут быть намного лучше, чем для общих задач покрытия/попадания множества. Более того, эти приближенные решения могут быть вычислены даже за почти линейное время. ^[3]

Алгоритмы аппроксимации

Жадный алгоритм для задачи покрытия общего множества дает приближение, где . Известно, что это приближение является точным с точностью до постоянного множителя. ^[4] Однако в геометрических условиях можно получить лучшие приближения. Используя алгоритм мультипликативного веса , ^[5] Бренниманн и Гудрич ^[6] показали, что -приближенное покрытие множества/набор попаданий для пространства диапазонов с постоянной размерностью VC может быть вычислено за полиномиальное время, где обозначает размер оптимального решения. Отношение приближения может быть дополнительно улучшено до или , когда индуцируется прямоугольниками или дисками, параллельными осям, в , соответственно. ${\displaystyle O(\log n)}$ ${\displaystyle n=\max\{|X|,|{\mathcal {R}}|\}}$ ${\displaystyle O(\log {\mathsf {OPT}})}$ ${\displaystyle \Sigma }$ ${\displaystyle {\mathsf {OPT}}\leq n}$ ${\displaystyle O(\log \log {\mathsf {OPT}})}$ ${\displaystyle O(1)}$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle \mathbb {R} ^{2}}$

Алгоритмы с почти линейным временем выполнения

Основываясь на технике итеративного перевеса Кларксона ^[7] и Бреннимана и Гудрича, ^[6] Агарвал и Пан ^[3] дали алгоритмы, которые вычисляют приблизительное покрытие множества/множество попаданий геометрического пространства диапазона во времени. Например, их алгоритмы вычисляют -приблизительное множество попаданий во времени для пространств диапазона, индуцированных двумерными прямоугольниками, параллельными осям; и он вычисляет -приблизительное покрытие множества во времени для пространств диапазона, индуцированных двумерными дисками. ${\displaystyle O(n~\mathrm {polylog} (n))}$ ${\displaystyle O(\log \log {\mathsf {OPT}})}$ ${\displaystyle O(n\log ^{3}n\log \log \log {\mathsf {OPT}})}$ ${\displaystyle O(1)}$ ${\displaystyle O(n\log ^{4}n)}$

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

• Установить проблему покрытия
• Крышка вершины
• Лебегово покрытие размерности
• Теорема Каратеодори о расширении

Ссылки

1. Фаулер, Р. Дж.; Патерсон, М. С.; Танимото, С. Л. (1981), «Оптимальная упаковка и покрытие на плоскости являются NP-полными», Inf. Process. Lett. , 12 (3): 133–137, doi :10.1016/0020-0190(81)90111-3
2. https://cs.uwaterloo.ca/~alopez-o/files/OtDUDCP_2011.pdf О проблеме покрытия диска дискретного блока
3. Агарвал, Панкадж К.; Пан, Цзянвэй (2014). «Почти линейные алгоритмы для геометрических множеств и покрытий множеств». Труды тридцатого ежегодного симпозиума по вычислительной геометрии .
4. Фейге, Уриэль (1998), «Порог ln n для аппроксимации покрытия множеств», Журнал ACM , 45 (4): 634–652, CiteSeerX 10.1.1.70.5014 , doi : 10.1145/285055.285059, S2CID  52827488 
5. Арора, С.; Хазан, Э.; Кейл, С. (2012), «Метод обновления мультипликативных весов: метаалгоритм и приложения», Теория вычислений , 8 : 121–164, doi : 10.4086/toc.2012.v008a006
6. Brönnimann, H.; Goodrich, M. (1995), «Почти оптимальные покрытия множеств в конечной размерности VC», Discrete & Computational Geometry , 14 (4): 463–479, doi : 10.1007/bf02570718
7. Кларксон, Кеннет Л. (1993-08-11). "Алгоритмы покрытия и аппроксимации многогранников". В Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; et al. (ред.). Алгоритмы и структуры данных . Конспект лекций по информатике. Том 709. Springer Berlin Heidelberg . стр. 246–252. doi :10.1007/3-540-57155-8_252. ISBN 978-3-540-57155-1.