Approximation error of 1-Lipschitz function on cubical mesh

Question

Let $\Omega = [0,1]^d$ and consider $f : \Omega \to R$ Lipschitz continuous with constant 1.

Consider the regular decomposition of $\Omega$ into $d$-dimensional cubes $\Omega_i$, $i=1 ... k^d$ with $k$ subdivision intervals along each dimension.

Consider the best approximation (in the sense of $ \| \cdot \|_\infty$) of $f$ by a function $\widehat f : \Omega \to R$, which is affine on each $\Omega_i$ and also Lipschitz continuous with constant 1 (and hence continuous).

I'm looking for an error/approximation bound $\| f - \widehat f \|_\infty \leq ...$ in terms of the mesh-size $k$ and dimension $d$.

EDIT: what makes this difficult for me is the requirement that $\widehat f$ is continuous. Since this is a global property, it seems very difficult to get a meaningful bound.

Answer 1

It's easy if $d = 1$, right? So the first case of interest is $d = 2$. Here is an example which shows why I think no nontrivial bound is possible.

(Of course you can always let $\hat{f}$ be a constant function which takes a value halfway between the max and min values of $f$; then $\|f - \hat{f}\|_\infty \leq \frac{\sqrt{d}}{2}$ since the max and min values of $f$ differ by at most the diameter of $[0,1]^d$, namely $\sqrt{d}$.)

Example: define $$f(x,y) = \begin{cases}x-y&\mbox{ if }x \geq y\cr y-x&\mbox{ if }y\geq x\end{cases}$$ on $[0,1]^2$. This has Lipschitz number $\sqrt{2}$, so feel free to scale it down by that factor if you like.

Now let $\hat{f}$ be any function on $[0,1]^2$ which is continuous and affine on each of the $k^2$ sub-squares. The key point is that $\hat{f}$ is determined by its values on the $x$ and $y$ axes. That is because an affine function on a square is determined by its values at the SW, SE, and NW corners of the square. So once we know $\hat{f}$ on the left and bottom boundaries of $[0,1]^2$, an easy double induction shows that we know it everywhere. Indeed, it is not hard to see that we must have $$\hat{f}(x,y) = \hat{f}(x,0) + \hat{f}(0,y) - \hat{f}(0,0)$$ at every point.

Now $f(1,0) = f(0,1) = 1$ and $f(0,0) = f(1,1) = 0$, but if $a = \hat{f}(0,0)$, $b = \hat{f}(1,0)$, and $c = \hat{f}(0,1)$ then $\hat{f}(1,1) = b + c - a$. So if $b$ and $c$ both exceed $\frac{1}{2}$ then one of $\hat{f}(0,0)$ and $\hat{f}(1,1)$ must exceed $\frac{1}{2}$, and this shows that $\|f - \hat{f}\|_\infty \geq \frac{1}{2}$ regardless of mesh.