Задача о геометрическом покрытии множества

Задача покрытия геометрических множеств является частным случаем задачи покрытия множеств в геометрических настройках. Входными данными является пространство диапазонов , где есть вселенная точек в и есть семейство подмножеств называемых диапазонов , определяемых пересечением и геометрических фигур, таких как диски и прямоугольники с параллельными осями. Цель состоит в том, чтобы выбрать подмножество диапазонов минимального размера таким образом, чтобы каждая точка во вселенной была покрыта некоторым диапазоном в .${\displaystyle \Сигма =(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 \Сигма}$${\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 \Сигма}$${\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 {полилог} (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)}$

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