View source for Ε-net (computational geometry)

{{Other uses|Ε-net (disambiguation){{!}}Ε-net}}
{{lowercase|title=ε-net}}
In [[computational geometry]], an '''''ε''-net''' (pronounced [[epsilon]]-net) is the approximation of a general set by a collection of simpler subsets. In [[probability theory]] it is the approximation of one probability distribution by another.

== Background ==

[[File:Unit square ɛ-net.svg|right|thumb|An ε-net with ε&nbsp;=&nbsp;1/4 of the unit square in the range space where the ranges are closed filled rectangles.]]
Let ''X'' be a set and R be a set of subsets of ''X''; such a pair is called a ''range space'' or [[hypergraph]], and the elements of ''R'' are called ''ranges'' or ''hyperedges''. An '''ε-net''' of a subset ''P'' of ''X'' is a subset ''N'' of ''P'' such that any range ''r''&nbsp;∈&nbsp;R with |''r''&nbsp;∩&nbsp;''P''|&nbsp;≥&nbsp;''ε''|''P''| intersects&nbsp;''N''.<ref name="HausslerWelzl1987">{{citation
 | last1 = Haussler | first1 = David | author1-link = David Haussler
 | last2 = Welzl | first2 = Emo | author2-link = Emo Welzl
 | doi = 10.1007/BF02187876
 | issue = 2
 | journal = [[Discrete & Computational Geometry]]
 | mr = 884223
 | pages = 127–151
 | title = ε-nets and simplex range queries
 | volume = 2
 | year = 1987| doi-access = free
 }}.</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;×&nbsp;[0,&nbsp;1]. Then the set N consisting of the 8 points shown in the adjacent diagram 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, there exists an ε-net of ''P'' of size

: <math>O\left(\frac{d}{\varepsilon} \log \frac{d}{\varepsilon}\right)\!;</math><ref name="HausslerWelzl1987"/>

because the size of this set is independent of ''P'', any set ''P'' can be described using a set of fixed size.

This facilitates the development of efficient [[approximation algorithm]]s. For example, suppose we wish to estimate an upper bound on the area of a given region, that falls inside a particular rectangle ''P''. One can estimate this to within an additive factor of ''ε'' times the area of ''P'' by first finding an ''ε''-net of ''P'', counting the proportion of elements in the ε-net falling inside the region with respect to the rectangle ''P'', and then multiplying by the area of&nbsp;''P''. The runtime of the algorithm depends only on ''ε'' and not&nbsp;''P''. One straightforward way to compute an ε-net with high probability is to take a sufficient number of random points, where the number of random points also depends only on&nbsp;''ε''. For example, in the diagram shown, any rectangle in the unit square containing at most three points in the 1/4-net has an area of at most&nbsp;3/8&nbsp;+&nbsp;1/4&nbsp;=&nbsp;5/8.

ε-nets also provide approximation algorithms for the [[NP-complete]] [[hitting set problem|hitting set]] and [[set cover problem|set cover]] problems.<ref>{{citation
 | last1 = Brönnimann | first1 = H.
 | last2 = Goodrich | first2 = M. T. | author2-link = Michael T. Goodrich
 | doi = 10.1007/BF02570718
 | issue = 4
 | journal = [[Discrete & Computational Geometry]]
 | mr = 1360948
 | pages = 463–479
 | title = Almost optimal set covers in finite VC-dimension
 | url = http://www.ics.uci.edu/~goodrich/pubs/setcover.ps
 | volume = 14
 | year = 1995| doi-access = free
 }}.</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 ==
{{reflist}}

{{DEFAULTSORT:E-net}}
[[Category:Computational geometry]]
[[Category:Probability theory]]