Changes between Version 1 and Version 2 of libpipi/sandbox Tweet

Timestamp:

10/22/2008 12:57:42 PM (16 years ago)

Author:

Sam Hocevar

Comment:

Cantor polynomial

libpipi/sandbox

@@ +1 @@
+== Numbering tiles ==
+
+If we want a straightforward way to linearly index tiles without necessarily knowing the image size, we can use the following enumeration:
+
+|| 0 || 1 || 3 || 6 || 10 || 15 || 21 ||
+|| 2 || 4 || 7 || 11 || 16 || 22 || 29 ||
+|| 5 || 8 || 12 || 17 || 23 || 30 || 38 ||
+|| 9 || 13 || 18 || 24 || 31 || 39 || … ||
+|| 14 || 19 || 25 || 32 || 40 || … || ||
+|| 20 || 26 || 33 || 41 || … || || ||
+|| 27 || 34 || 42 || … || || || ||
+
+One way to generate these values is using the '''Cantor polynomial''':
 {{{
 #!latex
-$\mbox{Var}[\tau(X_p,X_d)] = \mbox{Var}[E(\tau(X_p,X_d)|X_p)] E[\mbox{Var}(\tau(X_p,X_d)|X_p)]$
+$n = \dfrac{(x + y) (x + y + 1)}{2} + y$
 }}}
+
+Efficiently inverting that polynomial is not trivial. Here is one way to do it:
+{{{
+#!latex
+$k = E(\dfrac{\sqrt{8n+1}-1}{2})$
+
+$y = n - \dfrac{k (k + 1)}{2}$
+
+$x = k - y$
+}}}