# The existence of (non-rectangular) two dimensional Gray code

A Gray code consists of $$n$$-bit distinct strings $$s_1,s_2, \ldots,s_N$$ such that each $$s_i$$ and $$s_{i+1}$$ differs by one bit. For example: $$000, 001, 010, 011, 111, 110, 101, 100$$. It is known that we can have $$N=2^n$$ for every integer $$n$$.

A two-dimensional Gray code consists of $$m*n$$ strings $$s_{i,j}$$ for each $$1\leq i\leq m$$ and $$1\leq j\leq n$$, such that each $$s_{i,j}$$ and $$s_{i+1,j}$$ differs by one bit, each $$s_{i,j}$$ and $$s_{i,j+1}$$ differs by one bit, and each $$s_{i,j}$$ and $$s_{i+1,j+1}$$ differs by two bits. For example, the following is a $$4*4$$ Gray code using the optimal $$\log_2 4*4=4$$ bits.

0000, 0100, 1100, 1000

0001, 0101, 1101, 1001

0011, 0111, 1111, 1011

0010, 0110, 1110, 1010

It is not hard to construct $$m*n$$ 2d-gray codes using $$\log mn + O(1)$$ bits. My question is, if the "coordinates" $$(i,j)$$ does not form a rectangle (say, they lie arbitrarily on a grid), then is there an (almost) optimal 2d Gray code? That is, given $$N$$ coordinates $$X=\{(i,j)\}$$, can we construct a 2d Gray code for each $$s_{i,j}$$ using only $$\log N+O(1)$$ bits, for any $$N$$ and $$X$$?

• Nice question. Where is this applicable? Commented Apr 7, 2023 at 11:02
• Are holes between the $s_{i,j}$ allowed? (and - for example - the codes for $s_{i,j}$, $s_{i+2,j+2}$ must have hamming distance 4) Commented Apr 7, 2023 at 16:32
• @Turbo I think it would have some application in succinct encoding. Commented Apr 8, 2023 at 6:27
• @MarzioDeBiasi What do you mean by holes? In my mind the subgraph of a grid (induced by the coordinates) is connected, but there could be $(i,j)\in X$ and $(i+1,j)\notin X$. Commented Apr 8, 2023 at 6:34
• @MarzioDeBiasi the property you said does not hold when $(i+1,j),(i+2,j),(i+1,j+1),(i+2,j+1)\notin X$. Commented Apr 8, 2023 at 6:38