How many neighbours does a point in N-dim have?

Question

I am implementing an algortihm to find the neighbours of points in multidimensional grids. In 1D a point has two neighbours (left and right), in 2D there are 4 neighbour points (left, right, up, down) and in 3D there are 6. Now the figurative imagination comes to an end. How many neighbors does a point have in $N$ dimensions?

Is it just $2N$ ?

Answer 1

Let's say the grid is $\Bbb Z^n$ and let your point be $(p_1,p_2,\cdots,p_n)$. The adjacent vertices are the verices $(x_1,\cdots, x_n)$ such that:

1. for each $i$, $x_i-p_i\in\{-1,0,1\}$
2. there is exactly one index $j$ such that $x_j\ne p_j$.

Therefore, there are exactly $2n$ such vertices in the grid.

Answer 2

Yes, it's just $2N$.

You can see that algebraically (use the unit vectors in $N$ dimensional space $\mathbb{R}^N$) or with a geometric argument:

Think of building the $N$-cube by sliding the ($N-1$)-cube perpendicular to itself into the next dimension. Each facet of the ($N-1$)-cube traces out a facet of the $N$-cube. The original and final ($N-1$)-cubes are two more facets, so the number of facets increases by $2$ when the dimension increases by $1$.

https://en.wikipedia.org/wiki/Hypercube

Answer 3

When considering a hypercubical grid, then your quest just asks for the vertex count of the vertex figure of the according honeycomb. But as the vertex figure of the hypercubical honeycomb is just the orthoplex (cross-polytope), you clearly get 2N.

Alike you could derive the answer for any other grid too.

--- rk