Content deleted Content added
m Reverted 1 edit by 63.143.237.30 (talk) to last revision by Swpb. (TW) |
No edit summary |
||
Line 6:
== 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'' ∈ R with |''r'' ∩ ''P''| ≥ ''ε''|''P''| intersects ''N''.<ref>{{citation
| last1 = Haussler | first1 = David | author1-link = David Haussler
| last2 = Welzl | first2 = Emo | author2-link = Emo Welzl
| |||