2.2 Neighborhood size

Once the lattice is decided upon, we choose a neighborhood in which cells can interact. In the examples used so far, we have used the nearest neighbors only. The neighborhood is described by giving the set of cells that neighbor a given cell $(i,j)$. For the nearest neighbors on a square lattice, the neighborhood, which is called the von-Neumann neighborhood, is described by

$$N_{i,j} = \left\{ (k,l) \in {\cal L}\Bigm\vert \vert k-i\vert+\vert l-j\vert \le 1 \right\}.$$

Other common neighborhoods are the Moore neighborhood

$$N_{i,j} = \left\{ (k,l) \in {\cal L}\Bigm\vert \vert k-i\vert \le 1 \mbox{ and } \vert l-j\vert \le 1\right\}$$

and the obvious generalizations of the von-Neumann neighborhood to radius $r$,

$$N_{i,j} = \left\{ (k,l) \in {\cal L}\Bigm\vert \vert k-i\vert+\vert l-j\vert \le r \right\}$$

and the Moore neighborhood to radius $r$,

$$N_{i,j} = \left\{ (k,l) \in {\cal L}\Bigm\vert \vert k-i\vert \le r \mbox{ and } \vert l-j\vert \le r\right\}.$$

Of course, any other neighborhood can be defined (as long as it is uniform and finite). The mentioned neighborhoods are shown in Figure 2.6,

Figure 2.6: Examples for the different neighborhoods.

and the evolution of our example automaton with different neighborhoods is shown in Figures 2.7 and 2.8 (to be compared to Figure ). In this case the choice of the neighborhood affects the speed of wave propagation and the shape of the waves. In combination with a modification of the rules, the extension of the neighborhood sometimes leads to much better isotropy, and is therefore often used when natural phenomena are to be modeled. Note that a large neighborhood is usually very inefficient to simulate.

Applet 2.7: Example automaton using the Moore neighborhood with $r=1$.

Applet 2.8: Example automaton using the von Neumann neighborhood with $r=2$. Note that the wave spreads with a speed of 2 cells per time step.