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 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 there exists such that . If furthermore C is a subset of K, then it is an r-internal covering. The external covering number of K, denoted , is the minimum cardinality of any external covering of K. The internal covering number, denoted , is the minimum cardinality of any internal covering. A subset P of K is a packing if and the set is pairwise disjoint. The packing number of K, denoted , 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 , is the maximum cardinality of any r-separated subset of K. Examples Properties The following properties relate to covering numbers in the standard Euclidean space, : Application to machine learning Let be a space of real-valued functions, with the l-infinity metric (see example 3 above). Suppose all functions in are bounded by a real constant . Then, the covering number can be used to bound the generalization error of learning functions from , relative to the squared loss: where and is the number of samples. See also Polygon covering Kissing number References Topology Metric geometry