Problema de cobertura de conjunto geométrico

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

Dado el mismo espacio de rango , un problema estrechamente relacionado es el problema del conjunto impactante geométrico , donde el objetivo es seleccionar un subconjunto de puntos de tamaño mínimo tal que cada rango de tenga una intersección no vacía con , es decir, sea impactado por . ${\estilo de visualización \Sigma}$${\displaystyle H\subseteq X}$${\displaystyle {\mathcal {R}}}$${\estilo de visualización H}$${\estilo de visualización H}$

En el caso unidimensional, donde contiene puntos en la línea real y está definido por intervalos, tanto el problema de cobertura de conjuntos geométricos como el de conjuntos impactantes se pueden resolver 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 se induce por discos unitarios o cuadrados unitarios. ^[1] El problema de cobertura de discos unitarios discretos es una versión geométrica del problema de cobertura de conjuntos general que es NP-duro . ^[2]${\estilo de visualización X}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {R}}}$

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

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

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

• Problema con la cubierta del conjunto
• Cobertura de vértice
• Dimensión de la cubierta de Lebesgue
• Teorema de extensión de Carathéodory