Is there a way to map an infinite grid onto the natural numbers efficiently?

Question

I have a grid of cells that extends infinitely in all four directions. I need a way to map the coordinates of each cell to a unique positive integer efficiently. Can this be done non-sequentially? In other words, what is a function that is a bijection between $(\mathbb{Z},\mathbb{Z})$ and $(\mathbb{N})$?

Answer 1

I don't think this question is a duplicate of this other question - the aim is different - but the bijection there can be modified to fit this question.

First, define a mapping from $\mathbb{Z}$ to $\mathbb{N}$ as follows:

$$0 \mapsto 1$$

$$n \mapsto 2n\ \ (n>0)$$

$$-n \mapsto 2n+1\ \ (n>0)$$

So, the ordering is $0,1,-1,2,-2,\cdots$. Then, we use the mapping described in this question - given your (now positive) integer pair $(i,j)$, map it to $2^{i-1} (2j-1)$. Since each positive integer can be factored into a power of $2$ and an odd number uniquely, this is a bijective mapping.

For example, your pair $17,85$ would first map to the positive integer pair $34,170$. Then, we would map it to

$$2^{34}\cdot(2\cdot 170-1) = 5823975653376.$$

This might not be optimal if you want to actually calculate lots of correlations, but the underlying calculations are simple in nature.