3

It is well known that the sequence $x_n=nm\phi\bmod m$ where $\phi={1+\sqrt 5\over2}$ is the golden ratio can be used to generate an arbitrary amount of evenly spaced points in the interval $[0,m)$. Is there a similar series that generates evenly spaced points inside a rectangle of arbitrary dimensions?

FUZxxl
  • 9,307
  • What do you mean by "evenly spaced points inside a rectangle"? –  Mar 14 '17 at 20:46
  • 1
    @vrugtehagel I want that as $n\to\infty,$ the minimal distance between points is as high as possible. This is a practical question; I want to use such a sequence to choose colours out of a rectangular colour space such that they are pairwise easily distinguishable, even if we introduce additional colours from the series. – FUZxxl Mar 14 '17 at 20:53
  • Colors, at least the rgb colors used in computer screens, form a 3-dimensional space though. Furthermore, try putting $2$, $3$ and $4$ points in a square such that they're as far apart as possible. See what problems that creates? It's not going to look as pretty as $x_n=nm\phi$, and perhaps you should look for a more practical approach that might be mathematically inaccurate, but "good enough" for your project, for implementing the exact solution is going to create a much too computationally heavy function anyways. You can try equally spaced hues, which is much easier since hues are 1D. –  Mar 14 '17 at 20:55
  • @vrugtehagel I was thinking about using hue and brightness for the coordinates, leaving saturating free to express an attribute of the point (e.g. if it is “enabled” or “disabled.”). If I used all three dimensions of the colour space, I wouldn't be able to encode additional information at all. – FUZxxl Mar 14 '17 at 21:36

1 Answers1

5

The simplest traditional solution to the $d$-dimensional which provides quite good results in 2-dimensions is to use the Halton sequence based on the first two primes numbers (2,3). The Halton sequence is a generalization of the 1-dimensional Van der Corput sequence and merely requires that the two parameters are pairwise-coprime. Further details can be found at the Wikipedia article: "Halton Sequence".

An alternative sequence you could use is the generalization of the Weyl / Kronecker sequence. This sequence also typically uses the first two prime numbers, however, in this case they are chosen merely because the square root of these numbers is irrational.

However, I have recently written a detailed blog post "The unreasonable effectiveness of quasirandom sequences, on how to easily create an open-ended low discrepancy sequences in arbitrary dimensions, that is:

  • algebraically simpler
  • faster to compute
  • produces more consistent outputs
  • suffers less technical issues

than existing existing low discrepancy sequences, such as the Halton and Kronecker sequences.

The solution is an additive recurrence method (modulo 1) which generalizes the 1-Dimensional problem whose solution depends on the Golden Ratio. The solution to the $d$-dimensional problem, depends on a special constant $\phi_d$, where $\phi_d$ is the unique positive root of $ x^{d+1}=x+1$.

For $d=1$,  $ \phi_1 = 1.618033989... $, which is the canonical golden ratio.

And for $d=2$, $ \phi_2 = 1.3247179572... $, which  is often called the plastic constant, and has some beautiful properties. This value was conjectured to most likely be the optimal value for a related two-dimensional problem [Hensley, 2002].

A comparison of the various methods in 2-d is shown below.

enter image description here

Jacob Rus has posted a beautiful visualization of this 2-dimensional low discrepancy sequence, which can be found here.

With this special constant in hand, the calculation of the $n$-th term is now extremely simple and fast to calculate:

$$ R: \mathbf{t}_n = \pmb{\alpha}_0 + n \pmb{\alpha} \; (\textrm{mod} \; 1),  \quad n=1,2,3,... $$ $$ \textrm{where} \quad \pmb{\alpha} =(\frac{1}{\phi_d}, \frac{1}{\phi_d^2},\frac{1}{\phi_d^3},...\frac{1}{\phi_d^d}), $$

Of course, the reason this is called a recurrence sequence is because the above definition is equivalent to $$ R: \mathbf{t}_{n+1} = \mathbf{t}_{n} + \pmb{\alpha} \; (\textrm{mod} \; 1) $$

In nearly all instances, the choice of $\pmb{\alpha}_0 $ does not change the key characteristics, and so for reasons of obvious simplicity, $\pmb{\alpha}_0 =\pmb{0}$ is the usual choice. However, there are some arguments, relating to symmetry, that suggest that $\pmb{\alpha}_0=\pmb{1/2}$ is a better choice.

Specifically for $d=2$, $ \phi_2 = 1.3247179572... $ and so for $\pmb{\alpha}_0= (1/2,1/2) $, $$\pmb{\alpha} = (0.754878, 0.56984) $$ and so the first 5 terms of the canonical 2-dimensional sequence are:

  1. (0.254878, 0.0698403)
  2. (0.00975533, 0.639681)
  3. (0.764633, 0.209521)
  4. (0.519511, 0.779361)
  5. (0.274388, 0.349201)

Of course, this sequence ranges between [0,1], and so to convert to a range of [0,m], simply apply the linear transformation $ x:= mx $.

The Python code is

# Use Newton-Rhapson-Method
def gamma(d):
    x=1.0000
    for i in range(20):
        x = x-(pow(x,d+1)-x-1)/((d+1)*pow(x,d)-1)
    return x

d=2
n=5

g = gamma(d)
alpha = np.zeros(d)                 
for j in range(d):
    alpha[j] = pow(1/g,j+1) %1
z = np.zeros((n, d))    
for i in range(n):
    z = (0.5 + alpha*(i+1)) %1

print(z)

Hope that helps!

Martin Roberts
  • 1,779