Fixed two integers $d>1$ and $m>1$ let the mapping $g:[0,1]\longrightarrow [0,1]^{d}$ defined as
$g(t):=(t,\frac{1}{2}(1-\cos(m\pi t)), \ldots, \frac{1}{2}(1-\cos(m^{d-1}\pi t)))$
for all $t\in [0,1]$. A simple picture show that $g([0,1])$ "almost" fills the cube $[0,1]^{d}$, in the sense that for every $x\in [0,1]^{d}$ there exists some $t\in [0,1]$ such $\|x-g(t)\|\leq \frac{\sqrt{n-1}}{m}$, being $\|\cdot\|$ the Euclidean norm.
Consider the following algorithm:
Input: A point $x:=(x_{1},\ldots,x_{d})\in(0,1)^{d}$
Output: A point $t\in I$ such that $\|x-g(t)\|\leq \frac{\sqrt{n-1}}{m}$
Step 1: Put $t_{1}:=[m x_{1}]$ (the greatest integer less than or equal to $mx_{1}$).
Step 2: For $i$ from 2 to $d$ do
Compute $N:=\sum_{j=1}^{i-1} t_{j} m^{i-1-j}$ and a solution $u\in[0,1]$ of the eq. $ \frac{1}{2}(1-\cos(\pi u)) = (-1)^{N}(x_{i}-\frac{1}{2}) +\frac{1}{2}$.
Put $t_{i}:=[m u]$.
end do;
Step 3: Put $t_{d}:=mu$ ($u$ is computed in the above loop, specifically, the $u$ computed in the $d$-th iteration) and return $t:=\sum_{i=1}^{d}\frac{t_{i}}{m^{i}}$.
I have verified (in Maple) with many tests that the following pseudo-code, really, works out, that is, the returned $t\in [0,1]$ satisfies $\|x-g(t)\|\leq \frac{\sqrt{n-1}}{m}$. Some suggestion to give a formal proof of this?
On the other hand, I think that the computational comply of the above algorithm is an $O(d)$. Do you agree?
Many thanks in advance for your comments.
The key ideas here are
The number $t$ is being represented in base $m$, more or less.
The number of "wiggles" in dimension $k$ is roughly $m^k$. So to move through one whole "cycle" requires changing $t$ by about $\frac1{m^k}$
So: you start out by finding a value of $t$ that makes the first coordinate of $g(t)$ equal $x_1$, and such that changing $t$ by $\frac1m$ won't alter this by much.
Then you look at $x_2$: the second coordinate of $g(t)$ is almost certainly not $x_2$, but by adjusting $t$ by at most $\frac1m$, you can move through a whole cycle in the second coordinate, and not make the first coordinate change much. So you do so, adjusting $t$ so that the second coordinate of $g(t)$ is exactly $x_2$; this adjustment makes the first coordinate of $g(t)$ not quite $x_1$ anymore, but it doesn't screw it up by much.
Now you repeat. In total, you adjust the initial guess of $t$ by no more than a small amount, so $x_1$ is approximately matched; you adjust the SECOND guess of $t$ by an even smaller amount, so $x_2$ is approximately matched, and so on. And you get the LAST coordinate exactly, which is why the square root has an $n-1$ instead of an $n$ under it.
I assume that the $(-1)$-to-some-power thing is there to arrange that the series you sum up is an alternating series or something, but I could be wrong.