Equidistributed Point Sets

The classical goal of the theory of uniform distribution is the construction of well-distributed point sets and sequences; a classical example is the Hammersley point set in dimension two.

Consider integers , , with , and let be the binary expansion of . The Hammersley point set in dimension is defined by

The first coordinates of yield the van der Corput sequence for , and the second coordinates consecutively pass through the numbers . Figure 1 exhibits the behavior of both coordinates and . Note that the sequence orders the numbers in a balanced way in the upper and lower half of the unit interval .

Figure 1. Behavior of the coordinates and of the Hammersley point set for .

If we truncate bits from each coordinate of , we obtain a modified point set :

Using the function MyNet[m,t], the following graphics illustrate the structural behavior of . Figure 2 shows plots for and (from left to right).

Figure 2. Hammersley point set with bit truncation for and .

For increasing , the resolution of the points of decreases and therefore the distribution quality decreases as well. With even and , the point sets change from the well-distributed set (each grid line with resolution contains exactly one point) to the classical uniform lattice with points. In general, for the set , each grid line with resolution contains exactly points (see also Figure 3).

In more modern language, the point set is called a -net in base 2 and dimension ( is the parameter for the number of points and the parameter for the quality of distribution). The definition of an arbitrary -net requires a slightly modified form of the distribution property described earlier: every half-open elementary -dimensional subinterval of with volume has to contain exactly points. Figure 3 visualizes the latter requirement for and , . Some representative elementary two-dimensional intervals are indicated by colored rectangles (the lighter rectangles cover the darker ones). Note that the constant number of points within such intervals, by definition, must also be valid for all properly shifted elementary rectangles within .

Figure 3. Visualization of the -net property for and , .

A modern task in the theory of uniform distribution is the construction of arbitrary -nets with small parameters in large dimensions .