Counting points on a two-dimensional grid

Question

For some fixed $\bar{L}\in \mathbb N$, consider a set grid of points $$(i_1\;2^{−L_1},\ i_2\;2^{−L_2})$$ with $L_1,L_2 \in \mathcal L\equiv\{1,\dots,\bar{L}\}$, $i_1 \in \mathcal I(L_1)$, and $i_2 \in \mathcal I(L_2)$ where $$\mathcal I(L)\equiv\{i\in\mathbb N,\ 1\le i\le2^L-1,\ i \text{ odd}\}.$$

I want to find an explicit bijection between the set of indices of these grid points, i.e. $\mathcal L \times \mathcal L \times \mathcal I(L_1) \times\mathcal I(L_2)$, and $\mathbb N$.

---

This is a problem I ran into while trying to code an efficient way to interpolate hierarchical linear basis functions. So far I have, unfortunately, not made any advancements worth mentioning.

Answer 1

$\def\peq{\mathrel{\phantom{=}}{}}$Here it is assumed that $\overline{L}$ is a predetermined number. There are two bijections:\begin{align*} f_1(i_1 2^{-L_1}, i_2 2^{-L_2}) &= (2^{\overline{L}} - 1)(2^{L_1 - 1} - 1) + 2^{L_1 - 1}(2^{L_2 - 1} - 1) + 2^{L_2 - 1}\frac{i_1 - 1}{2} + \frac{i_2 - 1}{2},\\ f_2(i_1 2^{-L_1}, i_2 2^{-L_2}) &= (2^{\overline{L}} - 1)(2^{L_1 - 1} - 1) + (2^{\overline{L}} - 1) \frac{i_1 - 1}{2} + (2^{L_2 - 1} - 1) + \frac{i_2 - 1}{2}. \end{align*} The basic idea for constructing $f_1$ and $f_2$ is to sort grid points by $L_1, L_2, i_1, i_2$ or by $L_1, i_1, L_2, i_2$. The verification uses the same idea.

---

For $n$ dimensions, the grid points are$$ \left\{ \left( \frac{i_1}{2^{L_1}}, \cdots, \frac{i_n}{2^{L_n}} \right) \,\middle|\, 1 \leqslant L_k \leqslant L,\ 1 \leqslant i_k \leqslant 2^{L_k} - 1,\ i_k \text{ odd} \right\}, $$ and\begin{align*} f_1\left( \frac{i_1}{2^{L_1}}, \cdots, \frac{i_n}{2^{L_n}} \right) &= \sum_{k = 1}^n (2^{L_k - 1} - 1) (2^L - 1)^{n - k} \prod_{j = 1}^{k - 1} 2^{L_j - 1} + \sum_{k = 1}^n \frac{i_k - 1}{2} \prod_{j = k + 1}^n 2^{L_j - 1}\\ f_2\left( \frac{i_1}{2^{L_1}}, \cdots, \frac{i_n}{2^{L_n}} \right) &= \sum_{k = 1}^n \left(2^{L_k - 1} - 1 + \frac{i_k - 1}{2} \right) (2^L - 1)^{n - k}. \end{align*}

Answer 2

Maybe I’m missing something, but I don’t see why $\mathcal I(L_1)$ and $\mathcal I(L_2)$ are needed. I think your grid points are these: $(j_1 2^{-\bar L},j_2 2^{-\bar L})$ for $1\le j_1,j_2 \le 2^{\bar L}$. For example, if $\bar L=3$, your grid points are $(x,y)$ where $x$ and $y$ are in the set $\{\frac18,\frac28,\dots,\frac78\}$ Your “indices” are the numerator and log-denominator of the coordinates expressed in lowest terms.

For a fixed $\bar L$, you have $(2^{\bar L}-1)^2$ grid points. So first find a bijection from $\{1,2,...,(2^{\bar L}-1)^2\}$ to $\{(j_1,j_2)|1\le i_1,i_2 \le 2^{\bar L}\}$. Then compose it with the bijection that takes $j_k$ to $(o,e)$, where $o$ is the largest odd factor of $j_k$ and $e$ is $2^{\bar L}$divided by the largest even factor of $j_k$.