Ε-net (computational geometry): Difference between revisions

Revision as of 06:09, 19 January 2017

Latest revision as of 10:25, 26 April 2024

(5 intermediate revisions by 5 users not shown)

Line 1:

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

{{lowercase|title=ε-net}}

AnIn [[computational geometry]], 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 inIn [[probability theory]] where it is used to describe the approximation of one probability distribution by another.

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

[[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 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 and& Computational Geometry]]

| mr = 884223

| pages = 127–151

| title = ε-nets and simplex range queries

| volume = 2

| year = 1987| doi-access = free

| 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;×&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.

Line 23:

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.

Line 34:

| doi = 10.1007/BF02570718

| issue = 4

| journal = [[Discrete and& Computational Geometry]]

| mr = 1360948

| pages = 463–479

Line 40:

| url = http://www.ics.uci.edu/~goodrich/pubs/setcover.ps

| volume = 14

| year = 1995}}.</ref>| doi-access = free

}}.</ref>

== Probability theory ==