Math 2.0

Convex and discrete geometry Definition

Epsilon-net of a set system

Builds on Family of sets

Definition

Let XX be a finite nonempty set, let ℛ\mathcal{R} be a family of subsets of XX, called ranges, and let 0<ε≤10 < \varepsilon \le 1. A set N⊆XN \subseteq X is an ε\varepsilon-net of (X,ℛ)(X, \mathcal{R}) if every range R∈ℛR \in \mathcal{R} with ∣R∣≥ε∣X∣\abs{R} \ge \varepsilon \abs{X} satisfies R∩N≠∅R \cap N \ne \emptyset.

Remarks

Example: let X={1,2,…,100}X = \set{1, 2, \dots, 100}, let ℛ\mathcal{R} be the sets of the form {a,a+1,…,b}\set{a, a+1, \dots, b}, and let ε=1/10\varepsilon = 1/10. The set N={10,20,…,100}N = \set{10, 20, \dots, 100} is an ε\varepsilon-net. Indeed, a range with at least 1010 elements consists of at least 1010 consecutive integers, so it contains a multiple of 1010.

Non-example: for the same XX and ℛ\mathcal{R}, the set N′={20,40,…,100}N' = \set{20, 40, \dots, 100} is not a 1/101/10-net. The range {1,…,19}\set{1, \dots, 19} has 19≥1019 \ge 10 elements but misses N′N'.

The same notion is used for a probability measure μ\mu on a set XX: then NN is an ε\varepsilon-net if it meets every range RR with μ(R)≥ε\mu(R) \ge \varepsilon. The case above is μ\mu equal to the uniform measure on a finite XX.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Family of sets concept
  2. Epsilon-net of a set system definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Ε-net_(computational_geometry)
About this page
TagF7ZGDKRMB4
URIm2://F7ZGDKRMB4
Kinddefinition
WritingW0 stub
MSC52C45, 68U05, 05D05
DefinesEpsilon-net of a set system
UsesFamily of sets

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.