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. 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. It is one of the two most commonly used neighborhood types for two-dimensional cellular automata, the other one being the Moore neighborhood.
The von Neumann neighbourhood of a cell is the cell itself and the cells at a Manhattan distance of 1.
Von Neumann neighborhood of range r
An extension of the simple von Neumann neighborhood described above is to take the set of points at a Manhattan distance of r > 1. This results in a diamond-shaped region (shown for r = 2 in the illustration). These are called von Neumann neighborhoods of range or extent r. The number of cells in a 2-dimensional von Neumann neighborhood of range r can be expressed as . The number of cells in a d-dimensional von Neumann neighborhood of range r is the Delannoy number D(d,r). The number of cells on a surface of a d-dimensional von Neumann neighborhood of range r is the Zaitsev number (sequence A266213 in the OEIS).
- Moore neighborhood
- Neighbourhood (graph theory)
- Taxicab geometry
- Lattice graph
- Pixel connectivity
- Chain code
- Toffoli, Tommaso; Margolus, Norman (1987), Cellular Automata Machines: A New Environment for Modeling, MIT Press, p. 60.
- Ben-Menahem, Ari (2009), Historical Encyclopedia of Natural and Mathematical Sciences, Volume 1, Springer, p. 4632, ISBN 9783540688310.
- Wilson, Joseph N.; Ritter, Gerhard X. (2000), Handbook of Computer Vision Algorithms in Image Algebra (2nd ed.), CRC Press, p. 177, ISBN 9781420042382.
- Breukelaar, R.; Bäck, Th. (2005), "Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior", Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO '05), New York, NY, USA: ACM, pp. 107–114, doi:10.1145/1068009.1068024, ISBN 1-59593-010-8.