Ε-net (вычислительная геометрия) - Ε-net (computational geometry)

Для использования в других целях см. Ε-net.

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

Фон

Ε-сеть с ε = 1/4 единичного квадрата в пространстве диапазонов, где диапазоны представляют собой замкнутые закрашенные прямоугольники.

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

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

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

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

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

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

ε-сети также предоставляют алгоритмы аппроксимации для НП-полный ударная установка и установить обложку проблемы.^[2]

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

Позволять ${\displaystyle P}$ быть распределение вероятностей над некоторым набором ${\displaystyle X}$. An ${\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 .}$

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

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

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

Рекомендации

1. Хаусслер, Дэвид; Вельцль, Эмо (1987), "ε-сети и симплексные запросы диапазона", Дискретная и вычислительная геометрия, 2 (2): 127–151, Дои:10.1007 / BF02187876, МИСТЕР  0884223.
2. Brönnimann, H .; Гудрич, М. Т. (1995), «Почти оптимальные покрытия множеств в конечной VC-размерности», Дискретная и вычислительная геометрия, 14 (4): 463–479, Дои:10.1007 / BF02570718, МИСТЕР  1360948.