**Abstract:**
We present two partitioning algorithms that allow a sum of piecewise linear polynomials
over a number of overlaying convex partitions
of the unit cube $\Omega$ in $\RR^d$ to approximate a function $f\in W^3_p(\Omega)$
with the order $N^{-6/(2d+1)}$ in $L_p$-norm, where $N$ is the total number of cells of all partitions,
which makes a marked improvement over the $N^{-2/d}$ order achievable on a single convex
partition. The gradient of $f$ is approximated with the order $N^{-3/(2d+1)}$.
The first algorithm creates $d$ convex partitions and relies on the knowledge of the
eigenvectors of the average Hessians of $f$ over the cells of an auxiliary uniform partition,
whereas the second algorithm with $d+1\choose 2$ convex partitions is independent of $f$.
In addition, we also give an $f$-independent partitioning algorithm for a sum of $d$
piecewise constants that achieves the approximation order $N^{-2/(d+1)}$.

**Preprint version:**
pdf

Homepage