Zaitsev neighborhood

In a d-dimensional hypercube lattice (Cellular automaton), the generalized neighborhood comprises nodes which are situated at Chebyshev distance equal to 1 and Manhattan distance not greater than k, 1<=k<=d. Neighbors are connected via facets which are hypercubes having dimensions from d-1 to d-k. It means that the node coordinates difference contains no more than k nonzero components which are equal either to -1 or to 1. Thus, k=1 gives the Von Neumann neighborhood and k=d gives the Moore neighborhood.

For instance, for d=3, in a cube:

k=1 corresponds to von Neumann's neighborhood with 6 neighbors situated on facets and given with offsets {(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1)};

k=2 corresponds to 18 neighbors situated on facets and sides and given with offsets {(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1),(-1,-1,0),(-1,0,-1),(0,-1,-1),(-1,0,1),(-1,1,0),(0,-1,1),(0,1,-1),(1,0,-1),(1,-1,0),(1,1,0),(1,0,1),(0,1,1)};

k=3 corresponds to Moore's neighborhood with 26 neighbors situated on facets, sides and corners given with offsets {(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1),(-1,-1,0),(-1,0,-1),(0,-1,-1),(-1,0,1),(-1,1,0),(0,-1,1),(0,1,-1),(1,0,-1),(1,-1,0),(1,1,0),(1,0,1),(0,1,1),(-1,-1,-1),(1,-1,-1),(-1,1,-1),(1,1,-1),(-1,-1,1),(1,-1,1),(-1,1,1),(1,1,1)}.

The number of nodes in the generalized neighborhood is given with (sequence A265014 in OEIS) and represented with

$T(d,k) = \sum_{r=1}^{k} \binom{d}{r} 2^r$

or with a recurrent expression

$T(d,k) = T(d-1,k-1)-2T(d-1,k-2)+T(d-1,k)+T(d,k-1), T(d,1) = 2d, T(d,d) = 3^d-1.$

Parameter k allows adjusting density of the lattice neighboring cells in the range from the "sparsest" Von Neumann neighborhood at k=1 to the "densest" Moore neighborhood at k=d.

References

Zaitsev D.A. Generators of canvas for Petri net models of hypertorus (hypercube) grid with Moore's, von-Neumann's, and generalized neighborhoods. GitHub, 12 Nov 2015, https://github.com/dazeorgacm/hmn

Zaitsev D.A. Triangle read by rows: T(n,k) = number of neighbors in n-dimensional lattice for generalized neighborhood given with parameter k. The On-Line Encyclopedia of Integer Sequences, A265014, Nov 30 2015, http://oeis.org/A265014