ε-net (geometría computacional)
Un ε -net (pronunciado epsilon -net) en geometría computacional 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.
Sea X un conjunto y R un conjunto de subconjuntos de X ; tal par se llama espacio de rango o hipergráfico , y los elementos de R se denominan rangos o hipergrafias . Una red ε de un subconjunto P de X es un subconjunto N de P tal que cualquier rango r ∈ R con | r ∩ P | ≥ ε | P | intersecta N . [1] En otras palabras, cualquier rango que cruce al menos una proporción ε de los elementos deP también deben intersectar el ε -net N .
Por ejemplo, suponga que X es el conjunto de puntos en el plano bidimensional, R es el conjunto de rectángulos rellenos cerrados (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 una red de 1/4 de P, porque cualquier rectángulo relleno cerrado que intersecte al menos 1/4 del cuadrado unitario debe intersecar uno de estos puntos. De hecho, cualquier cuadrado (eje paralelo), independientemente del tamaño, tendrá una red similar de 8 puntos 1/4.
Para cualquier espacio de rango con dimensión finita de VC d , independientemente de la elección de P, existe una red ε de P de tamaño
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 queremos estimar un límite superior en el área de una región determinada, que cae dentro de un rectángulo en particular P . Se puede estimar esto dentro de un factor aditivo de ε veces 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 solo 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.
