Covering number

From formulasearchengine
Jump to navigation Jump to search

Template:Distinguish2

In mathematics, the idea of a covering number is to count how many small spherical balls would be needed to completely cover (with overlap) a given space. There are two closely related concepts as well, the packing number, which counts how many disjoint balls fit in a space, and the metric entropy, which counts how many points fit in a space when constrained to lie at some fixed minimum distance apart.

Mathematical Definition

More precisely, consider a subset of a metric space and a parameter . Denote the ball of radius centered at the point by . There are two notions of covering number, internal and external, along with the packing number and the metric entropy.

Inequalities and Monotonicity

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 .[1]

In addition, the quantities are non-increasing in and non-decreasing in for each of . However, monotonicity in can in general fail for .

References