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

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

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

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

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

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

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

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

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

См. также

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