Online algorithms to generate evenly distributed points in the unit square

Question

I am looking for online algorithms to generate points that are reasonably uniformly distributed in the unit square.

• The number of points is not known in advance. For every n, the distribution of the first n points generated must be reasonably uniformly distributed.

• The coordinates are real (floating-point) numbers (between 0 and 1); so, not on a grid.

• The points need (must) not be random; in fact, I want a deterministic algorithm, with provable properties (not based on statistics).

Generating such points in the unit interval can be done by using the golden ratio Phi:

• Take as point i the number (i * Phi) mod 1.

How to do that in 2D?

If the number of points is known in advance to be N, then ((Phi * i) mod 1, i/N) works nicely. But that is not online.

For some c, the points ((Phi * i) mod 1, (c * i) mod 1) could work, but it is not clear which c is best. Especially, for larger numbers of points, all c that I tried had clear deficiencies.

Answer 1

Martin Roberts (The Unreasonable Effectiveness of Quasirandom Sequences, 2018) recommends multiples of (1/φ₂, 1/φ₂²) where φ₂ = cbrt((9 + sqrt(69))/18) + cbrt((9 − sqrt(69))/18) is the plastic number.