ε-сеть (вычислительная геометрия)

В вычислительной геометрии ( ε- сеть произносится как эпсилон -сеть) — это аппроксимация общего множества набором более простых подмножеств. В теории вероятностей это аппроксимация одного распределения вероятностей другим.

Фон

Пусть X — множество, а R — множество подмножеств X ; такая пара называется пространством диапазонов или гиперграфом , а элементы R называются диапазонами или гиперребрами . ε -сеть подмножества P множества X — это подмножество N множества P такое, что любой диапазон r ∈ R такой, что | р ∩ П | ≥ ε | П | пересекает Н. ^{[ 1 ]} Другими словами, любой диапазон, который пересекает хотя бы часть ε элементов P, также пересекать ε -сеть N. должен

Например, предположим, что X — это набор точек на двумерной плоскости, R — это набор замкнутых закрашенных прямоугольников (произведений замкнутых интервалов), а P — это единичный квадрат [0, 1] × [0, 1]. Тогда множество N, состоящее из 8 точек, показанных на соседней диаграмме, представляет собой 1/4-сеть P, поскольку любой замкнутый закрашенный прямоугольник, пересекающий хотя бы 1/4 единичного квадрата, должен пересекать одну из этих точек. Фактически, любой (параллельный оси) квадрат, независимо от размера, будет иметь аналогичную 8-точечную развертку 1/4.

Для любого пространства значений с конечной размерностью VC d , независимо от выбора P, существует ε-сеть P размера

O\left({\frac {d}{\varepsilon }}\log {\frac {d}{\varepsilon }}\right)\!;

^{[ 1 ]}

поскольку размер этого набора не зависит от P , любой набор P можно описать, используя набор фиксированного размера.

Это облегчает разработку эффективных алгоритмов аппроксимации . Например, предположим, что мы хотим оценить верхнюю границу площади данной области, которая попадает в определенный прямоугольник P . Это можно оценить с точностью до аддитивного коэффициента, умноженного на ε, умноженного на площадь P , сначала найдя ε -сеть P , подсчитав долю элементов в ε-сети, попадающих внутрь области по отношению к прямоугольнику P , а затем умножив площади П. по Время работы алгоритма зависит только от ε а не от P. , Один простой способ вычислить ε-сеть с высокой вероятностью — взять достаточное количество случайных точек, причем количество случайных точек также зависит только от ε . Например, на показанной диаграмме любой прямоугольник в единичном квадрате, содержащий не более трех точек в 1/4-сети, имеет площадь не более 3/8 + 1/4 = 5/8.

ε-сети также предоставляют алгоритмы аппроксимации для NP-полного множества попаданий и задач покрытия множеств . ^{[ 2 ]}

Теория вероятностей

Позволять $P$ быть распределением вероятностей по некоторому множеству $X$ . Ан $\varepsilon$ -net для класса $H\subseteq 2^{X}$ подмножеств $X$ это любое подмножество $S\subseteq X$ такой, что для любого $h\in H$

P(h)\geq \varepsilon \quad \Longrightarrow \quad S\cap h\neq \varnothing .

Интуитивно $S$ аппроксимирует распределение вероятностей.

Более сильное понятие $\varepsilon$ -аппроксимация. Ан $\varepsilon$ -приближение к классу $H$ является подмножеством $S\subseteq X$ такой, что для любого $h\in H$ оно держится

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

Ссылки

^ Jump up to: ^а ^б Хаусслер, Дэвид ; Вельцль, Эмо (1987), «ε-сети и запросы симплексного диапазона», Discrete & Computational Geometry , 2 (2): 127–151, doi : 10.1007/BF02187876 , MR 0884223 .
^ Брённиманн, Х.; Гудрич, М.Т. (1995), «Покрытия почти оптимальных множеств в конечной VC-размерности» , Discrete & Computational Geometry , 14 (4): 463–479, doi : 10.1007/BF02570718 , MR 1360948 .

[HausslerWelzl1987-1] Jump up to: ^а ^б Хаусслер, Дэвид ; Вельцль, Эмо (1987), «ε-сети и запросы симплексного диапазона», Discrete & Computational Geometry , 2 (2): 127–151, doi : 10.1007/BF02187876 , MR 0884223 .

[2] Брённиманн, Х.; Гудрич, М.Т. (1995), «Покрытия почти оптимальных множеств в конечной VC-размерности» , Discrete & Computational Geometry , 14 (4): 463–479, doi : 10.1007/BF02570718 , MR 1360948 .

[ 1 ]

[ 2 ]