1

If I collapsed a 2 dimensional grid into 1 dimension (e.g a 3x3 grid into a string):

1 2 3
4 5 6     =>    1 2 3 4 5 6 7 8 9
7 8 9

Is there a formula where I could verify if two points used to be neighbors?

Working it out on a markerboard, the best I could come up with is:

(a % r) - (b % r) = {0,1}

Where a & b are the points and r is the row length.

This works well enough for handling the wrapping problem (e.g. 3 and 4 are not neighbors). But it thinks everything in the same column are neighbors. This formula would say that 1 and 7 are neighbors because (1%3)-(7%3) => 1-1 => 0.

Is there a way to correct that? I have no idea what I'm doing, so I may be approaching this the wrong way. I would not be surprised if there was an existing algorithm, and that ultimately is what I am after. I don't need my formula fixed, I'm just providing it to hopefully explain whats going on.

amflare
  • 153

2 Answers2

3

You are on the right track. If you write an $r\times r$ square matrix this way,

\begin{bmatrix} x_{0,0} & x_{0,1} & x_{0,2} & \dots & x_{0,r-1} \\ x_{1,0} & x_{1,1} & x_{1,2} & \dots & x_{1,r-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{r-1,0} & x_{r-1,1} & x_{r-1,2} & \dots & x_{r-1,r-1} \end{bmatrix}

the elements $x_{i,j}$ and $x_{k,\ell}$ are neighbors if and only if $|i-k|$ and $|j-\ell|$ add up to $1$.

Your matrix is indexed with one number:

\begin{bmatrix} a_{1} & a_{2} & a_{3} & \dots & a_{r} \\ a_{r+1} & a_{r+2} & a_{r+3} & \dots & a_{2r} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{r(r-1)+1} & a_{r(r-1)+2} & a_{r(r-1)+3} & \dots & a_{r^2} \end{bmatrix}

Therefore, if you can find functions $i(n)$ and $j(n)$ so that $a_n=x_{i(n),j(n)}$, the adjacency condition will be that $a_n$ is adjacent to $a_m$ if and only if

$$|i(n)-i(m)|+|j(n)-j(m)|=1.$$

The functions $i$ and $j$ aren’t hard to come up with. They are almost quotient and remainder modulo $r$, but since you are counting from $1$, not $0$, they are

$$ i(n)=(i-1)\backslash r\textrm { and } j(n)=(j-1)\% r,$$ where $\backslash$ is integer division (discarding remainder).

Note:If you want to consider an element its own neighbor, change $= 1$ in the formula to $\le 1$, and if you want to consider “diagonal neighbors,” change $|i(n)-i(m)|+|j(n)-j(m)|$ to $\max\left(|i(n)-i(m)|,|j(n)-j(m)|\right)$

Steve Kass
  • 14,881
1

Lets make a map from the linear index of your numbers to the rows and columns. I will assume your linear index starts with $0$ instead of $1$ to make the formulae simpler. Given a $n \times m$ integers $0, 1, \ldots, n\times m -1$ we want to arrange these into a grid of $n$ columns and $m$ rows: \begin{align*} &0& &\cdots& &n-1& \\ &n& &\cdots& &2n& \\ &\vdots& &\vdots& &\vdots&\\ &(m-1)\times n& &\cdots& &m\times n -1 \end{align*}

Now we want a function which gives us the row $r(x)$ and the column $c(x)$, lets assume these have values at $0 \ldots (m-1)$ and $0 \ldots (n-1)$ respectively.

Then given some linear index $x$ we know $x = n \times r(x) + c(x)$ so $c(x) = x \mod n$ and $r(x) = \frac{x- c(x)}{n}$.

Then given $x,y$ in your grid you can define a neighbor function:

$neighbor(x,y) \,\,\textrm{if}\,\, (r(x) = r(y) \pm 1 \,\,\textrm{and}\,\, c(x) = c(y))\,\, \textrm{or}]\,\, (r(x) = r(y) \,\,\textrm{and}\,\, c(x) = c(y) \pm 1) $.

Dominic Reiss
  • 374