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.

Definitions

If is a metric space, and is a subset of , then the packing radius, , of is half of the smallest distance between distinct members of . Open balls of radius centered at the points of will all be disjoint from each other. The covering radius, , of is the smallest distance such that every point of is within distance of at least one point in ; that is, is the smallest radius such that closed balls of that radius centered at the points of have all of as their union.

An -packing is a set of packing radius (equivalently, minimum distance ), an -covering is a set 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.

Construction of ''ε''-nets

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 have a well-ordering, transfinite induction shows that it is possible to construct an -net , by including in 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 ; thus, in this case, an -net can be constructed in linear time.

For more general finite or compact metric spaces, an alternative algorithm of Teo Gonzalez based on the farthest-first traversal can be used to construct a finite -net. This algorithm initializes the net to be empty, and then repeatedly adds to the farthest point in from , breaking ties arbitrarily and stopping when all points of  are within distance  of . In spaces of bounded doubling dimension, Gonzalez' algorithm can be implemented in time for point sets with a polynomial ratio between their farthest and closest distances, and approximated in the same time bound for arbitrary point sets..

Applications

Coding theory

In the theory of error-correcting codes, the metric space containing a block code consists of strings of a fixed length, say , taken over an alphabet of size (can be thought of as vectors), with the Hamming metric. This space is denoted by The covering radius and packing radius of this metric space are related to the code's ability to correct errors. An example is provided by the Berlekamp switching game.

Approximation algorithms

describe an algorithmic paradigm that they call "net and prune" for designing approximation algorithms for certain types of geometric optimization problems defined on sets of points in Euclidean spaces. An algorithm of this type works by performing the following steps:
#Choose a random point from the point set, find its nearest neighbor , and set to the distance between and .
#Test whether is (approximately) bigger than or smaller than the optimal solution value (using a technique specific to the particular optimization problem being solved)
#*If it is bigger, remove from the input the points whose closest neighbor is farther than
#*If it is smaller, construct an -net , and remove from the input the points that are not in .
In both cases, the expected number of remaining points decreases by a constant factor, so the time is dominated by the testing step. As they show, this paradigm can be used to construct fast approximation algorithms for k-center clustering, finding a pair of points with median distance, and several related problems.

A hierarchical system of nets, called a ''net-tree'', may be used in spaces of bounded doubling dimension to construct well-separated pair decompositions, geometric spanners, and approximate nearest neighbors.

Crystallography

For points in Euclidean space, a set is a Meyer set if it is relatively dense and its difference set is uniformly discrete. Equivalently, is a Meyer set if both and are Delone sets. Meyer sets are named after Yves Meyer, who introduced them (with a different but equivalent definition based on harmonic analysis) as a mathematical model for quasicrystals. They include the point sets of lattices, Penrose tilings, and the Minkowski sums of these sets with finite sets.

The Voronoi cells of symmetric Delone sets form space-filling polyhedra called plesiohedra..

References

External links

Delone set
– Tilings Encyclopedia

{{Metric spaces

Metric geometry