Ε-net (computational geometry): Difference between revisions

Revision as of 02:14, 14 September 2010

Latest revision as of 10:25, 26 April 2024

(21 intermediate revisions by 17 users not shown)

Line 1:

{{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.

{{Other uses|ε-net}}

An '''ε-net''' (pronounced [[epsilon]]-net) describes several related concepts in [[mathematics]] and, in particular, in compuational geometry where it relates to the approcimation of a general set by a collection of simpler subsets.

== Background ==

[[File:Unit square ɛ-net.svg|right|thumb|An ε-net with ε = 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>D. Haussler and E. Welzl. ε-nets and simplex range queries. Discrete and Computational Geometry, 2:127–151, 1987.</refname="HausslerWelzl1987"> In other words, any range that intersects at least a proportion ε of the elements of P must also intersect the ε-net N.{{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] &timesnbsp;×&nbsp; [0,&nbsp;1]. Then the set RN consisting of the 8 points shown in the adjacent 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 <math>O\left(\frac{d}{\epsilon} \log \frac{d}{\epsilon}\right)</math>; because the size of this set is independent of P, any set P can be described using a set of fixed size.

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

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 P that falls inside a particular rectangle. 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 rectangle, and then multiplying by the area of P. The runtime of the algorithm depends only on ɛ and not 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 ɛ. For example, in the diagram shown, any rectangle in the unit square containing at most 3 points in the 1/4-net has an area of at most 3/8 + 1/4 = 5/8.

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

ɛ-nets also provide approximation algorithms for the [[NP-complete]] [[hitting set problem|hitting set]] and [[set cover problem|set cover]] problems.<ref>H. Brönnimann and [[Michael T. Goodrich|M. T. Goodrich]]. Almost optimal set covers in finite VC dimensions. Discrete and Computational Geometry, 14:463–479, 1995. [http://www.ics.uci.edu/~goodrich/pubs/setcover.ps (Postscript)]</ref>

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 P, 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 3three points in the 1/4-net has an area of at most &nbsp;3/8 &nbsp;+ &nbsp;1/4 &nbsp;= &nbsp;5/8.

== References ==

ε-nets also provide approximation algorithms for the [[NP-complete]] [[hitting set problem|hitting set]] and [[set cover problem|set cover]] problems.<ref>{{citation

<references/>

| 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]]