Ε-net (computational geometry): Difference between revisions

Revision as of 01:42, 17 March 2012

Revision as of 01:11, 19 March 2013

Line 1:

{{Other uses|Ε-net (disambiguation){{!}}Ε-net}}

{{lowercase|title=ε-net}}

An '''''ε''-net''' (pronounced [[epsilon]]-net) is any of several related concepts in [[mathematics]], and in particular in [[computational geometry]], where it relates to the approximation of a general set by a collection of simpler subsets. It has a particular meaning in [[probability theory]] where it is used to describe the approximation of one probability distribution by another.

== Background ==

Line 20 ⟶ 19:

| year = 1987}}.</ref> In other words, any range that intersects at least a proportion ε of the elements of ''P'' must also intersect the ''ε''-net&nbsp;''N''.

For example, suppose ''X'' is the set of points in the two-dimensional plane, ''R'' is the set of closed filled rectangles (products of closed intervals), and ''P'' is the unit square [0,&nbsp;1]&nbsp;&times;×&nbsp;[0,&nbsp;1]. Then the set N consisting of the 8 points shown in the diagram to the right is a 1/4-net of P, because any closed filled rectangle intersecting at least 1/4 of the unit square must intersect one of these points. In fact, any (axis-parallel) square, regardless of size, will have a similar 8-point 1/4-net.

For any range space with finite [[VC dimension]] ''d'', regardless of the choice of P and ε, there exists an ε-net of ''P'' of size

Line 42 ⟶ 41:

| volume = 14

| year = 1995}}.</ref>

== Probability theory ==

Let <math>P</math> be a [[probability distribution]] over some set <math>X</math>. An '''<math>\varepsilon</math>-net''' for a class <math>H \subseteq 2^X</math> of subsets of <math>X</math> is any subset <math>S \subseteq X</math> such that

for any <math>h \in H</math>

:<math>P(h) \ge \varepsilon \quad \Longrightarrow \quad S\cap h \neq \varnothing.</math>

Intuitively <math>S</math> approximates the probability distribution.

A stronger notion is <math>\varepsilon</math>-approximation. An '''<math>\varepsilon</math>-approximation''' for class <math>H</math> is a subset <math>S \subseteq X</math> such that for any <math>h \in H</math> it holds

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

== References ==

Line 48 ⟶ 60:

{{DEFAULTSORT:E-net}}

[[Category:Computational geometry]]

[[Category:Probability theory]]

[[vi:Lưới ε (hình học tính toán)]]