Optimal approximation order of piecewise constants on convex partitions

Abstract We prove that the error of the best nonlinear L p -approximation by piecewise constants on convex partitions is O ( N − 2 d + 1 ) , where N is the number of cells, for all functions in the Sobolev space W q 2 ( Ω ) on a cube Ω ⊂ R d , d ⩾ 2 , as soon as 2 d + 1 + 1 p − 1 q ⩾ 0 . The approximation order O ( N − 2 d + 1 ) is achieved on a polyhedral partition obtained by anisotropic refinement of an adaptive dyadic partition. Further estimates of the approximation order from the above and below are given for various Sobolev and Sobolev–Slobodeckij spaces W q r ( Ω ) embedded in L p ( Ω ) , some of which also improve the standard estimate O ( N − 1 d ) known to be optimal on isotropic partitions.