ε-net (geometría computacional)

En geometría computacional , una ε -red (pronunciada epsilon -red) es la aproximación de un conjunto general por 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 red ε con ε = 1/4 del cuadrado unitario en el espacio de rango donde los rangos son rectángulos rellenos cerrados.

Sea X un conjunto y R un conjunto de subconjuntos de X ; dicho par se denomina espacio de rangos 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 y rellenos (productos de intervalos cerrados) y P es el cuadrado unitario [0, 1] × [0, 1]. Entonces, el conjunto N que consiste en los 8 puntos que se muestran en el diagrama adyacente es una red 1/4 de P, porque cualquier rectángulo cerrado y relleno que interseca al menos 1/4 del cuadrado unitario debe intersecar uno de estos puntos. De hecho, cualquier cuadrado (paralelo al eje), independientemente de su tamaño, tendrá una red 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]

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 dada, que cae dentro de un rectángulo particular P . Uno puede estimar esto dentro de un factor aditivo de ε por 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 sencilla de calcular una ε-red con alta probabilidad es tomar un número suficiente de puntos aleatorios, donde el número 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 redes ε también proporcionan algoritmos de aproximación para los problemas de cobertura y de conjunto de impacto NP-completos . ^[2]

Teoría de la probabilidad

Sea una distribución de probabilidad sobre algún conjunto . Una -red 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 .}$

Se aproxima intuitivamente a la distribución de probabilidad. ${\displaystyle S}$

Una noción más fuerte es la de -aproximación. Una -aproximación para una clase es un subconjunto tal que para cualquier valor que se cumpla ${\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. Haussler, David ; Welzl, Emo (1987), "ε-nets y consultas de rango simplex", Geometría discreta y computacional , 2 (2): 127–151, doi : 10.1007/BF02187876 , MR  0884223.
2. Brönnimann, H.; Goodrich, MT (1995), "Coberturas de conjuntos casi óptimas en dimensión VC finita", Geometría discreta y computacional , 14 (4): 463–479, doi : 10.1007/BF02570718 , MR  1360948.