Uniformly discrete set

In the mathematical theory of metric spaces, ε-nets, ε-packings, ε-coverings, uniformly discrete sets, relatively dense sets, and Delone sets (named after Boris Delone) are several closely related definitions of well-spaced sets of points, and the packing radius and covering radius of these sets measure how well-spaced they are. These sets have applications in coding theory, approximation algorithms, and the theory of quasicrystals.

If (M,d) is a metric space, and X is a subset of M, then the packing radius of X is half of the infimum of distances between distinct members of X. If the packing radius is r, then open balls of radius r centered at the points of X will all be disjoint from each other, and each open ball centered at one of the points of X with radius 2r will be disjoint from the rest of X. The covering radius of X is the infimum of the numbers r such that every point of M is within distance r of at least one point in X; that is, it is the smallest radius such that closed balls of that radius centered at the points of X have all of M as their union. An ε-packing is a set X of packing radius ≥ ε/2 (equivalently, minimum distance ≥ ε), an ε-covering is a set X of covering radius ≤ ε, and an ε-net is a set that is both an ε-packing and an ε-covering. A set is uniformly discrete if it has a nonzero packing radius, and relatively dense if it has a finite covering radius. A Delone set is a set that is both uniformly discrete and relatively dense; thus, every ε-net is Delone, but not vice versa.

As the most restrictive of the definitions above, ε-nets are at least as difficult to construct as ε-packings, ε-coverings, and Delone sets. However, whenever the points of M have a well-ordering, transfinite induction shows that it is possible to construct an ε-net N, by including in N every point for which the infimum of distances to the set of earlier points in the ordering is at least ε. For finite sets of points in a Euclidean space of bounded dimension, each point may be tested in constant time by mapping it to a grid of cells of diameter ε, and using a hash table to test which nearby cells already contain points of N; thus, in this case, an ε-net can be constructed in linear time.

...
Wikipedia