The Halton sequence can be used like a random number generator to produce points in the interval [0,1]. The Halton sequence is even less random than a random number generator; if you specify the index I of the Halton number you want, there is a formula for producing H(I). On the other hand, the Halton sequence does a better job of filling in the region, avoiding the large gaps that can occur with a random number generator.

The idea is simple. We choose a base, let's say 2. As a normal person counts from I = 1, 2, 3, ... we take each value I, write it in base 2, and reverse the digits, including the decimal sign, and convert back to base 10:

1 = 1.0 => 0.1 = 1/2 2 = 10.0 => 0.01 = 1/4 3 = 11.0 => 0.11 = 3/4 4 = 100.0 => 0.001 = 1/8 5 = 101.0 => 0.101 = 5/8 6 = 110.0 => 0.011 = 3/8 7 = 111.0 => 0.111 = 7/8and so on.

How can we program this? We just need to read the next digit of the base two representation of I, then subtract it from I and divide by two. Then we have to add to H(I) the new digit times the next power of 1/2. I've written down a sketch of what a program might look like:

The number I is input. The number H is output. H = 0 half = 1 / 2 do while ( I is not zero ) digit = mod ( I, 2 ) H = H + digit * half I = ( I - digit ) / 2 half = half / 2 endTo do this for base 3, just replace all the 2's by 3's.

Now to get a "good" sequence of Halton points in 2D, we compute the X coordinates using a base of 2, and the Y coordinates using a base of 3. (If we wanted Z as well, we'd use a base of 5 for that, and successive primes for more dimensions). You can store all the bases in a vector. and do the computations in a very compact way.

See if you can use this information, plus the text of the FORTRAN routine I_TO_HALTON_VECTOR, to produce a set of Halton points for 2D. The idea is that your CVT program would have 3 different ways of generating a set of initial cell generators: the Monte Carlo or random number method, the uniform grid method, and the Halton points.

Back to the Voronoi Project page.

Last modified on 20 June 2001.