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