Problema de cobertura de conjuntos geométricos

El problema de cobertura de conjuntos geométricos es un caso especial del problema de cobertura de conjuntos en entornos geométricos. La entrada es un espacio de rangos.${\displaystyle \Sigma =(X,{\mathcal {R}})}$dónde${\displaystyle X}$es un universo de puntos en${\displaystyle \mathbb {R} ^{d}}$y${\displaystyle {\mathcal {R}}}$es una familia de subconjuntos de${\displaystyle X}$llamados rangos , definidos por la intersección de${\displaystyle X}$y formas geométricas como discos y rectángulos paralelos a los ejes. El objetivo es seleccionar un subconjunto de tamaño mínimo.${\displaystyle {\mathcal {C}}\subseteq {\mathcal {R}}}$de rangos tales que cada punto del universo${\displaystyle X}$está cubierto por algún rango en${\displaystyle {\mathcal {C}}}$.

Dado el mismo rango de espacio${\displaystyle \Sigma }$Un problema estrechamente relacionado es el problema del conjunto de colisión geométrico , donde el objetivo es seleccionar un subconjunto de tamaño mínimo.${\displaystyle H\subsetequ X}$de puntos tales que cada rango de${\displaystyle {\mathcal {R}}}$tiene intersección no vacía con${\displaystyle H}$, es decir, es golpeado por${\displaystyle H}$.

En el caso unidimensional, donde${\displaystyle X}$contiene puntos en la línea real y${\displaystyle {\mathcal {R}}}$está definido por intervalos, tanto el problema de cobertura de conjuntos geométricos como el problema del conjunto de colisión pueden resolverse en tiempo polinomial utilizando un algoritmo voraz simple . Sin embargo, en dimensiones superiores, se sabe que son NP-completos incluso para formas simples, es decir, cuando${\displaystyle {\mathcal {R}}}$es inducido por discos unitarios o cuadrados unitarios. ^{[ 1 ]} El problema de la cobertura de discos unitarios discretos es una versión geométrica del problema general de cobertura de conjuntos que es NP-difícil . ^{[ 2 ]}

Se han ideado numerosos algoritmos de aproximación para estos problemas. Debido a su naturaleza geométrica, las razones de aproximación para estos problemas pueden ser mucho mejores que las de los problemas generales de cobertura de conjuntos/conjuntos de colisión. Además, estas soluciones aproximadas pueden incluso calcularse en tiempo casi lineal. ^{[ 3 ]}

El algoritmo voraz para el problema general de cobertura de conjuntos da como resultado${\displaystyle O(\log n)}$aproximación, donde${\displaystyle n=\max\{|X|,|{\mathcal {R}}|\}}$. Se sabe que esta aproximación es precisa salvo por un factor constante. ^{[ 4 ]} Sin embargo, en entornos geométricos, se pueden obtener mejores aproximaciones. Utilizando un algoritmo de ponderación multiplicativa , ^{[ 5 ]} Brönnimann y Goodrich ^{[ 6 ]} demostraron que una${\displaystyle O(\log {\mathsf {OPT}})}$-cobertura de conjunto aproximada/conjunto de golpeo para un espacio de campo de tiro${\displaystyle \Sigma }$con dimensión VC constante se puede calcular en tiempo polinomial, donde${\displaystyle {\mathsf {OPT}}\leq n}$denota el tamaño de la solución óptima. La relación de aproximación se puede mejorar aún más para${\displaystyle O(\log \log {\mathsf {OPT}})}$o${\displaystyle O(1)}$cuando${\displaystyle {\mathcal {R}}}$es inducido por rectángulos o discos paralelos a los ejes en${\displaystyle \mathbb {R} ^{2}}$, respectivamente.

Basándose en la técnica iterativa de reponderación de Clarkson ^{[ 7 ]} y Brönnimann y Goodrich, ^{[ 6 ]} Agarwal y Pan ^{[ 3 ]} dieron algoritmos que calculan una cobertura de conjunto aproximada/conjunto de colisión de un espacio de rango geométrico en${\displaystyle O(n~\mathrm {polylog} (n))}$tiempo. Por ejemplo, sus algoritmos calculan un${\displaystyle O(\log \log {\mathsf {OPT}})}$-ajuste de golpeo aproximado en${\displaystyle O(n\log ^{3}n\log \log \log {\mathsf {OPT}})}$tiempo para espacios de rango inducidos por rectángulos paralelos a los ejes 2D; y calcula un${\displaystyle O(1)}$-cobertura aproximada del conjunto en${\displaystyle O(n\log ^{4}n)}$tiempo para espacios de rango inducidos por discos 2D.

• Problema de la cubierta del conjunto
• cobertura de vértices
• Dimensión de cobertura de Lebesgue
• Teorema de extensión de Carathéodory