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.
Fondo
Sea X un conjunto y R un conjunto de subconjuntos de X ; dicho par se denomina espacio de rango o hipergráfico , y los elementos de R se denominan rangos o hipergrafias . Un ε-net 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 se cruza con al menos un ε proporción de los elementos de P 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 sólo de ε y no 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 redes ε también proporcionan algoritmos de aproximación para los problemas de cobertura de conjuntos y conjuntos de golpes NP-completos . [2]
Teoría de probabilidad
Dejar ser una distribución de probabilidad sobre algún conjunto. Un-net para una clase de subconjuntos de es cualquier subconjunto tal que para cualquier
Intuitivamente aproxima la distribución de probabilidad.
Una noción más fuerte es -aproximación. Un-aproximación por clase es un subconjunto tal que para cualquier se mantiene
Referencias
- ^ Haussler, David ; Welzl, Emo (1987), "ε-nets and simplex range queries", Discrete and Computational Geometry , 2 (2): 127-151, doi : 10.1007 / BF02187876 , MR 0884223.
- ^ Brönnimann, H .; Goodrich, MT (1995), "Cubiertas de conjuntos casi óptimos en dimensión VC finita" , Geometría discreta y computacional , 14 (4): 463–479, doi : 10.1007 / BF02570718 , MR 1360948.