Covering number

cosmos 30th October 2018 at 5:29pm

The ϵ\epsilon-covering number of BχB \subseteq \chi, denoted by N(ϵ;B)N(\epsilon;B), is the size of the smallest set ABA \subseteq B such that for every bB b \in B there is an aA a \in A such that ρ(a;b)<ϵ\rho(a;b) < \epsilon, where ρ\rho is a Metric on χ\chi.

The ϵ\epsilon-Packing number gives an upper bound, and the 2ϵ2\epsilon-packing number gives a lower bound (this is because removing a point from a 2ϵ2\epsilon packing would result in something that isn't an ϵ\epsilon cover, as can be shown using the Triangle inequality)

See here and here

See also UML