ε-net (geometría computacional)

En geometría computacional , una ε -net (pronunciada épsilon -net) 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 por otra.

Fondo

Una ε-net con ε = 1/4 del cuadrado unitario en el espacio de rango donde los rangos son rectángulos cerrados y rellenos.

Sea X un conjunto y R un conjunto de subconjuntos de X ; dicho par se llama espacio de rangos o hipergrafo , y los elementos de R se llaman rangos o hiperbordes . Una ε-net de un subconjunto P de X es un subconjunto N de P tal que cualquier rango r  ∈ R con | r  ∩  PAG | ≥  ε | P | cruza  N . ^[1] En otras palabras, cualquier rango que cruce al menos una proporción ε de los elementos de P también debe cruzar la ε -net  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 que consta de los 8 puntos que se muestran en el diagrama adyacente es un 1/4 neto de P, porque cualquier rectángulo cerrado y relleno que corte al menos 1/4 del cuadrado unitario debe cruzar uno de estos puntos. De hecho, cualquier cuadrado (paralelo al eje), independientemente de su tamaño, tendrá una red similar de 1/4 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]

debido a 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 en el área de una región determinada, que cae dentro de un rectángulo particular P. Se puede estimar esto dentro de un factor aditivo de ε multiplicado por el área de P encontrando primero una ε -net de P , contando la proporción de elementos en la ε-net 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 sólo de ε y no  de P. Una forma sencilla 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 que se muestra, cualquier rectángulo en el cuadrado unitario que contenga como máximo tres puntos en la red de 1/4 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 cobertura de conjuntos y conjuntos de bateo NP-completos . ^[2]

Teoría de la probabilidad

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

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

Aproxima intuitivamente la distribución de probabilidad. ${\displaystyle S}$

Una noción más fuerte es la aproximación. Una aproximación para clase es un subconjunto tal que para cualquiera se cumple ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle H}$ ${\displaystyle S\subseteq X}$ ${\displaystyle h\in H}$

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

Referencias

1. abHaussler, David ; Welzl, Emo (1987), "ε-nets y consultas de rango simplex", Geometría computacional y discreta , 2 (2): 127–151, doi : 10.1007/BF02187876 , SEÑOR  0884223.
2. Brönnimann, H.; Goodrich, MT (1995), "Cubiertas de conjuntos casi óptimas en dimensiones finitas de VC", Geometría computacional y discreta , 14 (4): 463–479, doi : 10.1007/BF02570718 , MR  1360948.