ε-net(컴퓨터 기하학)

계산기하학에서 ε-넷(epsilon-net)은 단순한 부분집합들의 집합에 의한 일반 집합의 근사치입니다. 확률 이론에서 이것은 한 확률 분포를 다른 확률 분포에 의한 근사치입니다.

배경

X를 집합, R을 X의 부분집합이라고 하자; 이러한 쌍을 범위 공간 또는 하이퍼그래프라고 하고, R의 원소를 범위 또는 하이퍼그래프라고 합니다. X의 부분 집합 P의 ε-넷은 r ∩ P ∈ P를 갖는 임의의 범위 R이 N과 교차하도록 P의 부분 집합 N입니다. 즉, P의 원소들의 적어도 비율 ε과 교차하는 어떤 범위도 ε-넷 N과 교차해야 합니다.

예를 들어, X를 2차원 평면의 점들의 집합, R을 닫힌 채워진 직사각형의 집합(닫힌 간격의 곱), P를 단위 제곱[0, 1] × [0, 1]이라고 가정합니다. 그러면 단위 사각형의 적어도 1/4과 교차하는 닫힌 채워진 직사각형은 이 점들 중 하나와 교차해야 하므로, 인접 다이어그램에 표시된 8개의 점으로 구성된 집합 N은 P의 1/4-넷입니다. 실제로 크기에 관계없이 임의의 (축 평행) 정사각형은 비슷한 8점 1/4-넷을 가질 것입니다.

유한 VC 차원 d를 갖는 임의의 범위 공간에 대하여, P의 선택에 관계없이 크기가 P인 ε-넷이 존재합니다.

${\displaystyle O\left({\frac {d}{\varepsilon}}\log {\frac {d}{\varepsilon}}\right)\!;}$^[1]

이 집합의 크기는 P와 무관하므로 고정된 크기의 집합을 사용하여 임의의 집합 P를 설명할 수 있습니다.

이를 통해 효율적인 근사 알고리즘을 개발할 수 있습니다. 예를 들어 특정 직사각형 P 안에 들어가는 주어진 영역의 면적에 대한 상한을 추정하려고 한다고 가정해 보자. 먼저 P의 ε-넷을 찾고, 직사각형 P에 대해 영역 내부에 있는 ε-넷의 요소의 비율을 계산한 다음, P의 면적을 곱함으로써 이것을 P의 면적의 ε배의 가산 계수 내에서 추정할 수 있습니다. 알고리즘의 런타임은 ε에만 의존하고 P에는 의존하지 않습니다. 높은 확률로 ε-넷을 계산하는 한 가지 간단한 방법은 충분한 수의 난수점을 취하는 것이며, 난수점의 수 역시 ε에만 의존합니다. 예를 들어, 표시된 다이어그램에서 1/4-net의 최대 세 점을 포함하는 단위 사각형의 직사각형은 최대 3/8 + 1/4 = 5/8의 면적을 갖습니다.

ε-넷은 또한 NP-완전 타격 세트 및 세트 커버 문제에 대한 근사 알고리즘을 제공합니다.

확률론

$P{\displaystyle }$ ${\displaystyle P}$를 일부 집합 $X{\displaystyle }$ ${\displaystyle X}$에 대한 확률 분포라고 가정합니다$.$ An ${\displaystyle \varepsilon }$-net for a class ${\displaystyle H\subseteq 2^{X}}$ of subsets of ${\displaystyle X}$ is any subset ${\displaystyle S\subseteq X}$ such that for any ${\displaystyle h\in H}$

${\displaystyle P(h)\geq \varepsilon \quad \longright 화살표 \quad S\cap h\neq \varnothing.}$

$직관적$으로 S ${\displaystyle$ S$}$는 확률 분포를 근사합니다$$.

더 강력한 개념은$$ε ${\$displaystyle \varepsilon} - 근사입니다. $클래스$ H ${\$displaystyle \varepsilon} - $클래스$ $H$ ${\displaystyle$ H}에 대한 근사치는 $임의의 H$$$∈$$H {\displaystyle H\in H}에$$대해 $유지$되는${\displaystyle }$${\displaystyle \mathrm{부분}}$ 집합$S$ ⊆ $X${\$displaystyle$S\subseteq X}입니다.

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

참고문헌