Covering number

Not to be confused with Winding number or degree of a continuous mapping, sometimes called "covering number" or "engulfing 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.

Definition

Let (M, d) be a metric space, let K be a subset of M, and let r be a positive real number. Let B_r(x) denote the ball of radius r centered at x. A subset C of M is an external covering if $K\subseteq \cup _{x\in C}B_{r}(x)$ . If furthermore C is a subset of K, then it is an internal covering.

The external covering number of K, denoted $N_{r}^{\text{ext}}(K)$ , is the minimum cardinality of any external covering of K. The internal covering number, denoted $N_{r}^{\text{int}}(K)$ , is the minimum cardinality of any internal covering.

A subset P of K is a packing if $\cup _{x\in P}B_{r}(x)\subseteq K$ and the set $\{B_{r}(x)\}_{x\in P}$ is pairwise disjoint. The packing number of K, denoted $N_{r}^{\text{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}^{\text{met}}(K)$ , is the maximum cardinality of any r-separated subset of K.

Properties

The internal and external covering numbers, the packing number, and the metric entropy are all closely related. The following chain of inequalities holds for any subset K of a metric space and any positive real number r.^[1]

N_{2r}^{\text{met}}(K)\leq N_{r}^{\text{pack}}(K)\leq N_{r}^{\text{ext}}(K)\leq N_{r}^{\text{int}}(K)\leq N_{r}^{\text{met}}(K)

In addition, each function except the internal covering number is non-increasing in r and non-decreasing in K. The internal covering number is monotone in r but not necessarily in K.

References

↑ Tao, Terrance. "Metric entropy analogues of sum set theory". Retrieved 2 June 2014.

This article is issued from Wikipedia - version of the 11/15/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.