Von Neumann neighborhood

Manhattan distance r = 1
Manhattan distance r = 2

In cellular automata, the von Neumann neighborhood (or 4-neighborhood) is classically defined on a two-dimensional square lattice and is composed of a central cell and its four adjacent cells.[1] The neighborhood is named after John von Neumann, who used it to define the von Neumann cellular automaton and the von Neumann universal constructor within it.[2] It is one of the two most commonly used neighborhood types for two-dimensional cellular automata, the other one being the Moore neighborhood.

This neighbourhood can be used to define the notion of 4-connected pixels in computer graphics.[3]

The von Neumann neighbourhood of a cell is the cell itself and the cells at a Manhattan distance of 1.

The concept can be extended to higher dimensions, for example forming a 6-cell octahedral neighborhood for a cubic cellular automaton in three dimensions.[4]

  1. ^ Toffoli, Tommaso; Margolus, Norman (1987), Cellular Automata Machines: A New Environment for Modeling, MIT Press, p. 60.
  2. ^ Ben-Menahem, Ari (2009), Historical Encyclopedia of Natural and Mathematical Sciences, Volume 1, Springer, p. 4632, ISBN 9783540688310.
  3. ^ Wilson, Joseph N.; Ritter, Gerhard X. (2000), Handbook of Computer Vision Algorithms in Image Algebra (2nd ed.), CRC Press, p. 177, ISBN 9781420042382.
  4. ^ Cite error: The named reference bb05 was invoked but never defined (see the help page).