Covering number

In mathematics, a covering number is the number of spherical balls of a given size needed to completely cover a given space, with possible overlaps. Two related concepts are the packing number, the number of disjoint balls that fit in a space, and the metric entropy, the number of points that fit in a space when constrained to lie at some fixed minimum distance apart. In mathematics, a covering number is the number of spherical balls of a given size needed to completely cover a given space, with possible overlaps. Two related concepts are the packing number, the number of disjoint balls that fit in a space, and the metric entropy, the number of points that fit in a space when constrained to lie at some fixed minimum distance apart. Let (M, d) be a metric space, let K be a subset of M, and let r be a positive real number. Let Br(x) denote the ball of radius r centered at x. A subset C of M is an r-external covering of K if: In other words, for every y ∈ K {displaystyle yin K} there exists x ∈ C {displaystyle xin C} such that d ( x , y ) ≤ r {displaystyle d(x,y)leq r} . If furthermore C is a subset of K, then it is an r-internal covering. The external covering number of K, denoted N r ext ( K ) {displaystyle N_{r}^{ ext{ext}}(K)} , is the minimum cardinality of any external covering of K. The internal covering number, denoted N r int ( K ) {displaystyle N_{r}^{ ext{int}}(K)} , is the minimum cardinality of any internal covering. A subset P of K is a packing if P ⊆ K {displaystyle Psubseteq K} and the set { B r ( x ) } x ∈ P {displaystyle {B_{r}(x)}_{xin P}} is pairwise disjoint. The packing number of K, denoted N r pack ( K ) {displaystyle N_{r}^{ ext{pack}}(K)} , is the maximum cardinality of any packing of K. A subset S of K is r-separated if each pair of points x and y in S satisfies d(x, y) ≥ r. The metric entropy of K, denoted N r met ( K ) {displaystyle N_{r}^{ ext{met}}(K)} , is the maximum cardinality of any r-separated subset of K. 1. The metric space is the real line R {displaystyle mathbb {R} } . K ⊂ R {displaystyle Ksubset mathbb {R} } is a set of real numbers whose absolute value is at most k {displaystyle k} . Then, there is an external covering of ⌈ 2 k / r ⌉ {displaystyle lceil 2k/r ceil } intervals of length r {displaystyle r} , covering the interval [ k , − k ] {displaystyle } . Hence: 2. The metric space is the Euclidean space R m {displaystyle mathbb {R} ^{m}} with the Euclidean metric. K ⊂ R m {displaystyle Ksubset mathbb {R} ^{m}} is a set of vectors whose length (norm) is at most k {displaystyle k} .If K {displaystyle K} lies in a d-dimensional subspace of R m {displaystyle mathbb {R} ^{m}} , then::337