ε-net (geometría computacional)

En geometría computacional , una ε -red (pronunciada épsilon -red) es la aproximación de un conjunto general mediante una colección de subconjuntos más simples. En teoría de la probabilidad, es la aproximación de una distribución de probabilidad mediante otra.

Sea X un conjunto y R un conjunto de subconjuntos de X ; dicho par se denomina espacio rango o hipergrafo , y los elementos de R se denominan rangos o hiperaristas . Una ε-red de un subconjunto P de X es un subconjunto N de P tal que cualquier rango r  ∈  R con | r  ∩ P | ≥ ε | P | interseca a N. ^{[ 1 ]} En otras palabras, cualquier rango que interseca al menos una proporción ε de los elementos de P también debe intersecar la ε -red N.     

Por ejemplo, supongamos que X es el conjunto de puntos en el plano bidimensional, R es el conjunto de rectángulos cerrados rellenos (productos de intervalos cerrados) y P es el cuadrado unitario [0,  1]  ×  [0,  1]. Entonces, el conjunto N, formado por los 8 puntos mostrados en el diagrama adyacente, es una red de 1/4 de P, ya que cualquier rectángulo cerrado relleno que interseque al menos 1/4 del cuadrado unitario debe intersecar uno de estos puntos. De hecho, cualquier cuadrado (paralelo a los ejes), independientemente de su tamaño, tendrá una red de 1/4 similar de 8 puntos.

Para cualquier espacio de rango con dimensión VC finita d , independientemente de la elección de P, existe una ε-red de P de tamaño

${\displaystyle O\left({\frac {d}{\varepsilon }}\log {\frac {d}{\varepsilon }}\right)\!;}$^{[ 1 ]}

Dado que el tamaño de este conjunto es independiente de P , cualquier conjunto P puede describirse utilizando un conjunto de tamaño fijo.

Esto facilita el desarrollo de algoritmos de aproximación eficientes . Por ejemplo, supongamos que deseamos estimar un límite superior para el área de una región dada, que cae dentro de un rectángulo particular P. Se puede estimar esto dentro de un factor aditivo de ε veces el área de P encontrando primero una ε -red de P , contando la proporción de elementos en la ε-red que caen dentro de la región con respecto al rectángulo P , y luego multiplicando por el área de P. El tiempo de ejecución del algoritmo depende solo de ε y no de P. Una forma directa de calcular una ε-red con alta probabilidad es tomar una cantidad suficiente de puntos aleatorios, donde la cantidad de puntos aleatorios también depende solo de ε . Por ejemplo, en el diagrama mostrado, cualquier rectángulo en el cuadrado unitario que contenga como máximo tres puntos en la 1/4-red tiene un área de como máximo 3/8 + 1/4 = 5/8.        

Las ε-nets también proporcionan algoritmos de aproximación para los problemas de conjunto de colisión y cobertura de conjuntos NP-completos . ^{[ 2 ]}

Dejar${\displaystyle P}$sea ​​una distribución de probabilidad sobre algún conjunto${\displaystyle X}$. Un${\displaystyle \varepsilon }$-net para una clase${\displaystyle H\subseteq 2^{X}}$de subconjuntos de${\displaystyle X}$es cualquier subconjunto${\displaystyle S\subsetequ X}$de tal manera que para cualquier${\displaystyle h\in H}$

${\displaystyle P(h)\geq \varepsilon \quad \Longrightarrow \quad S\cap h\neq \varnothing .}$

Intuitivamente${\displaystyle S}$se aproxima a la distribución de probabilidad.

Una noción más fuerte es${\displaystyle \varepsilon }$-aproximación. Una${\displaystyle \varepsilon }$-aproximación para la clase${\displaystyle H}$es un subconjunto${\displaystyle S\subsetequ X}$de tal manera que para cualquier${\displaystyle h\in H}$lo sostiene

${\displaystyle \left|P(h)-{\frac {|S\cap h|}{|S|}}\right|<\varepsilon .}$