Von Neumann neighborhood
Encyclopedia
In cellular automata, the von Neumann neighborhood comprises the four cells orthogonally surrounding a central cell on a two-dimensional square lattice
. The neighborhood is named after John von Neumann
, who used it for his pioneering cellular automata
including the Universal Constructor
. It is one of the two most commonly used neighborhood types, the other one being the 8-cell Moore neighborhood
. It is similar to the notion of 4-connected pixel
s in computer graphics
.
The concept can be extended to higher dimensions, for example forming a 6-cell octahedral
neighborhood for a cubic cellular automaton in three dimensions.
The von Neumann neighbourhood of a point is the set of points at a Manhattan distance of 1.
Square lattice
In mathematics, the square lattice is a type of lattice in a two-dimensional Euclidean space. It is the two-dimensional version of the integer lattice. It is one of the five types of two-dimensional lattices as classified by their symmetry groups; its symmetry group is known symbolically as p4m.Two...
. The neighborhood is named after John von Neumann
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
, who used it for his pioneering cellular automata
Von Neumann cellular automata
Von Neumann cellular automata are the original expression of cellular automata, the development of which were prompted by suggestions made to John von Neumann by his close friend and fellow mathematician Stanisław Ulam...
including the Universal Constructor
Von Neumann universal constructor
John von Neumann's Universal Constructor is a self-replicating machine in a cellular automata environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann's book Theory of Self-Reproducing Automata, completed in...
. It is one of the two most commonly used neighborhood types, the other one being the 8-cell Moore neighborhood
Moore neighborhood
In cellular automata, the Moore neighborhood comprises the eight cells surrounding a central cell on a two-dimensional square lattice. The neighborhood is named after Edward F. Moore, a pioneer of cellular automata theory. It is one of the two most commonly used neighborhood types, the other one...
. It is similar to the notion of 4-connected pixel
Pixel
In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....
s in computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
.
The concept can be extended to higher dimensions, for example forming a 6-cell octahedral
Octahedron
In geometry, an octahedron is a polyhedron with eight faces. A regular octahedron is a Platonic solid composed of eight equilateral triangles, four of which meet at each vertex....
neighborhood for a cubic cellular automaton in three dimensions.
The von Neumann neighbourhood of a point is the set of points 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 - the MathWorld link below has a nice diagram of what such neighborhoods look like. These are called von Neumann neighborhoods of range or extent r.See also
- Neighbourhood (graph theory)Neighbourhood (graph theory)In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. For example, the image shows a...
- Taxicab geometryTaxicab geometryTaxicab geometry, considered by Hermann Minkowski in the 19th century, is a form of geometry in which the usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their coordinates...
- Lattice graphLattice graphThe terms lattice graph, mesh graph, or grid graph refer to a number of categories of graphs whose drawing corresponds to some grid/mesh/lattice, i.e., its vertices correspond to the nodes of the mesh and its edges correspond to the ties between the nodes.-Square grid graph:A common type of a...
- Pixel connectivityPixel connectivityIn image processing and image recognition, pixel connectivity is the way in which pixels in 2- or 3-dimensional images relate to their neighbors.-4-connected:...