El problema de la cobertura del conjunto geométrico es el caso especial del problema de la cobertura del conjunto en entornos geométricos. La entrada es un espacio de rango dónde es un universo de puntos en y es una familia de subconjuntos de llamados rangos , definidos por la intersección dey formas geométricas como discos y rectángulos paralelos a los ejes. El objetivo es seleccionar un subconjunto de tamaño mínimo de rangos tales que cada punto del universo está cubierto por algún rango en .
Dado el mismo espacio de rango , un problema estrechamente relacionado es el problema del conjunto de golpes geométricos , donde el objetivo es seleccionar un subconjunto de tamaño mínimo de puntos de modo que cada rango de tiene una intersección no vacía con , es decir, es golpeado por.
En el caso unidimensional, donde contiene puntos en la recta real yse define por intervalos, tanto la cobertura de conjuntos geométricos como los problemas de conjuntos de aciertos se pueden resolver en tiempo polinomial utilizando un algoritmo codicioso simple . Sin embargo, en dimensiones más altas, se sabe que son NP-completos incluso para formas simples, es decir, cuandoes inducida por discos unitarios o cuadrados unitarios. [1] El problema de la cubierta del disco de la unidad discreta es una versión geométrica del problema de la cubierta del conjunto general que es NP-hard . [2]
Se han ideado muchos algoritmos de aproximación para estos problemas. Debido a la naturaleza geométrica, las relaciones de aproximación para estos problemas pueden ser mucho mejores que los problemas generales de cobertura de conjuntos / conjuntos de golpes. Además, estas soluciones aproximadas pueden calcularse incluso en un tiempo casi lineal. [3]
Algoritmos de aproximación
El algoritmo codicioso para el problema de cobertura del conjunto general da aproximación, donde . Se sabe que esta aproximación se ajusta al 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-conjunto aproximado de cobertura / golpe 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 para o Cuándo es inducida por rectángulos o discos paralelos a los ejes en , respectivamente.
Algoritmos de tiempo casi lineal
Basado 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 un conjunto aproximado de cobertura / impacto de un espacio de rango geométrico enhora. Por ejemplo, sus algoritmos calculan un- golpe aproximado establecido en tiempo para espacios de rango inducidos por rectángulos paralelos de ejes 2D; y calcula un-Cubierta aproximada en tiempo para espacios de rango inducidos por discos 2D.
Ver también
Referencias
- ^ Fowler, RJ; Paterson, MS; Tanimoto, SL (1981), "El embalaje y el recubrimiento óptimos en el avión son NP-completos", Inf. Proceso. Letón. , 12 (3): 133–137, doi : 10.1016 / 0020-0190 (81) 90111-3
- ^ https://cs.uwaterloo.ca/~alopez-o/files/OtDUDCP_2011.pdf Sobre el problema de la cubierta del disco de la unidad discreta
- ^ a b Agarwal, Pankaj K .; Pan, Jiangwei (2014). "Algoritmos casi lineales para conjuntos de golpes geométricos y cubiertas de conjuntos". Actas del trigésimo simposio anual sobre geometría computacional .
- ^ Feige, Uriel (1998), "Un umbral de ln n para aproximar la cobertura del conjunto", Journal of the ACM , 45 (4): 634–652, CiteSeerX 10.1.1.70.5014 , doi : 10.1145 / 285055.285059
- ^ Arora, S .; Hazan, E .; Kale, S. (2012), "The Multiplicative Weights Update Method: a Meta-Algorithm and Applications", Theory of Computing , 8 : 121-164, doi : 10.4086 / toc.2012.v008a006
- ^ a b Brönnimann, H .; Goodrich, M. (1995), "Cubiertas de conjuntos casi óptimas en dimensión VC finita", Geometría discreta y computacional , 14 (4): 463–479, doi : 10.1007 / bf02570718
- ^ Clarkson, Kenneth L. (11 de agosto de 1993). "Algoritmos para cubrimiento y aproximación de politopos". En Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; et al. (eds.). Algoritmos y estructuras de datos . Apuntes de conferencias en Ciencias de la Computación. 709 . Springer Berlín Heidelberg . págs. 246-252. doi : 10.1007 / 3-540-57155-8_252 . ISBN 978-3-540-57155-1.