Can every Lipschitz function be approximated by functions of constant variation? Suppose $f:\mathbb R^d\to \mathbb R$ is 1-Lipschitz (with respect to the 2-norm), and $\epsilon > 0$.
Can we always find a function $g$, such that:


*

*$g$ is 1-Lipschitz,

*$\lVert\nabla g\rVert_2 = 1$ a.e

*$\lVert g-f\rVert_\infty < \epsilon$?


If not, what if $f$ is also $C^1$, or if we restrict the domain to $I=[0,1]^d$?
For $d=1$, the proof is fairly simple, we can just take $g(0)=f(0)$, and for positive $x$, we set the derivative of $g$ to 1 until the difference surpasses $\epsilon$, then switch the derivative to $-1$, and so on.
The difference between two consecutive changes will be bounded below by $\epsilon/2$, so the function is properly defined for all $x>0$.
We can then do the same thing for negative $x$.
I can't seem to generalize this method for $d \geq 2$, though.
 A: This is a proof that Rahul's construction satisfies the requirements.

Let $h(x,y)=f(y) + \lVert x-y \rVert_2$, and
$$g(x) = \min_{y\in \left(\epsilon/\sqrt d\right) \mathbb Z^d} h(x,y).$$
We have $ f(x) \leq h(x,y)$, so $f \leq g$
Let us show that $g \leq f+\epsilon$.  
$$g(x) \leq \min_{y\in \left(\epsilon/\sqrt d\right) \mathbb Z^d} f(y) + \lVert x-y\rVert_2 \leq \min_{y\in \left(\epsilon/\sqrt d\right) \mathbb Z^d} f(x)+2\lVert x-y\rVert_2 \leq  f(x) + 2d(x,\left(\epsilon/\sqrt d\right) \mathbb Z^d).$$
Let $x\in \mathbb R^d$, $n\in \left(\epsilon/\sqrt d\right) \mathbb Z^d$ s.t $x\in n+\left[0, \epsilon/\sqrt d\right]^d$, and $X$ the extreme points of this set.
We have $d\left(x,\left(\epsilon/\sqrt d\right) \mathbb Z^d\right) \leq d(x, X)\leq \operatorname{diam}(X) = \epsilon/2$.
So $g \leq f+\epsilon$.
Let us show that $g$ is 1-Lipschitz.
Let $x,x' \in \mathbb R^d$.
$$\begin{align}
g(x) &= \min_{y\in \left(\epsilon/\sqrt d\right) \mathbb Z^d} f(y) + \lVert x-y\rVert_2, \\
&\leq \min_{y\in \left(\epsilon/\sqrt d\right) \mathbb Z^d} f(y) + \lVert x'-y\rVert_2 + \lVert x-x'\rVert_2, \\
&\leq g(x') + \lVert x-x'\rVert_2, \\
g(x)-g(x')&\leq \lVert x-x'\rVert_2.
\end{align}$$
Similarly we show that $$g(x')-g(x)\leq \lVert x-x'\rVert_2.$$
So $g$ is 1-Lipschitz.
$g$ must therefore be differentiable a.e.
Let $x$ be a point where $g$ is differentiable s.t $x\notin \left(\epsilon/\sqrt d\right) \mathbb Z^d$ and $x, y, y'$ are never colinear for any $y,y' \in \left(\epsilon/\sqrt d\right) \mathbb Z^d$.
We show that $\min_{y\in \left(\epsilon/\sqrt d\right) \mathbb Z^d} h(x,y)$ is attained at a single point $y^\star$. From that, it's not difficult to show that $y^\star$ minimizes $h(x',y)$ over $\left(\epsilon/\sqrt d\right) \mathbb Z^d$ for all $x'$ in some neighborhood of $x$.
Suppose the minimum is attained at $y_1,\dots, y_n$.
$$g(x) = f(y_1) + \lVert x-y_1\rVert_2 = \dots = f(y_n) + \lVert x-y_n\rVert_2.$$
$$\exists \alpha >: \forall x'\in B(x, \alpha): g(x') = \min (f(y_1) + \lVert x'-y_1\rVert_2, \dots, f(y_n) + \lVert x'-y_n\rVert_2)$$
Suppose $n > 1$.
Since the $n$ functions all have different gradients at $x$, they separate the ball into $n$ regions, each containing a cone with an origin at $x$, and non-empty interior.
In each cone we can take a basis of $\mathbb R^d$, and define the gradient from the slopes along the vectors. The limits of the slopes will correspong to the gradient of the function associated with the region. And since the gradients they result in don't match, $g$ can't be differentiable at $x$. Which gives a contradiction.  
Therefore the minimum is attained at a single point $y^\star$, which remains the same in a neighborhood of $x$, and proves that $$\nabla g(x) = \frac{x-y^\star}{\lVert x-y^\star \rVert_2}.$$
So $\lVert\nabla g(x)\rVert_2 = 1.$
