Contar puntos en una cuadrícula bidimensional

Question

Para algunos fijos $\bar{L}\in \mathbb N$ Consideremos un conjunto de puntos $$(i_1\;2^{L_1},\ i_2\;2^{L_2})$$ con $L_1,L_2 \in \mathcal L\equiv\{1,\dots,\bar{L}\}$ , $i_1 \in \mathcal I(L_1)$ y $i_2 \in \mathcal I(L_2)$ donde $$\mathcal I(L)\equiv\{i\in\mathbb N,\ 1\le i\le2^L-1,\ i \text{ odd}\}.$$

Quiero encontrar una biyección explícita entre el conjunto de índices de estos puntos de la cuadrícula, es decir $\mathcal L \times \mathcal L \times \mathcal I(L_1) \times\mathcal I(L_2)$ y $\mathbb N$ .

---

Este es un problema con el que me topé mientras intentaba codificar una forma eficiente de interpolar funciones de base lineal jerárquicas. Hasta ahora, lamentablemente, no he hecho ningún avance digno de mención.

Answer 1

Tal vez me estoy perdiendo algo, pero no veo por qué $\mathcal I(L_1)$ y $\mathcal I(L_2)$ son necesarios. Creo que sus puntos de rejilla son estos: $(j_1 2^{-\bar L},j_2 2^{-\bar L})$ para $1\le j_1,j_2 \le 2^{\bar L}$ . Por ejemplo, si $\bar L=3$ sus puntos de la cuadrícula son $(x,y)$ donde $x$ y $y$ están en el conjunto $\{\frac18,\frac28,\dots,\frac78\}$ Sus "índices" son el numerador y el log-denominador de las coordenadas expresadas en términos mínimos.

Para un fijo $\bar L$ , usted tiene $(2^{\bar L}-1)^2$ puntos de la cuadrícula. Por lo tanto, primero hay que encontrar una biyección desde $\{1,2,...,(2^{\bar L}-1)^2\}$ a $\{(j_1,j_2)|1\le i_1,i_2 \le 2^{\bar L}\}$ . Entonces compóngalo con la biyección que toma $j_k$ a $(o,e)$ , donde $o$ es el mayor factor impar de $j_k$ y $e$ es $2^{\bar L}$ dividido por el mayor factor par de $j_k$ .

Answer 2

$\def\peq{\mathrel{\phantom{=}}{}}$ Aquí se supone que $\overline{L}$ es un número predeterminado. Hay dos biyecciones: $$\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*}$$ La idea básica para construir $f_1$ y $f_2$ es ordenar los puntos de la cuadrícula por $L_1, L_2, i_1, i_2$ o por $L_1, i_1, L_2, i_2$ . La verificación utiliza la misma idea.

---

Para $n$ dimensiones, los puntos de la cuadrícula son $$\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\},$$ y $$\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*}$$