Packing number

cosmos 30th May 2019 at 8:02pm

Let AχA \subseteq \chi and ϵ>0\epsilon > 0. We say that A is ϵ\epsilon-separated if ρ(x;y)ϵ\rho(x;y) \geq \epsilon for all x,yAx,y \in A, where ρ\rho is a Metric over the set χ\chi.

The ϵ\epsilon-packing number of BXB \subseteq X, denoted by M(ϵ;B)\mathcal{M}(\epsilon;B) is the size of the largest ϵ\epsilon-separated set contained in BB.

It is the same as the size of the largest number of centers of balls of size ϵ/2\epsilon/2 we can pack inside the set BB, hence why it's called the packing number.

Note that if a point in BB is further from all points in AA than ϵ\epsilon, we can always add one more point to AA, therefore the maximal packing set (of size M(ϵ;B)\mathcal{M}(\epsilon;B)), has all points in BB within less than distance ϵ\epsilon of points in AA, and it is therefore a covering set. Therefore, M(ϵ;B)\mathcal{M}(\epsilon;B) is an upper bound on the Covering number

See here and here and UML